UNIST, CSE 3th

1 minute read

1962. Remove Stones to Minimize the Total (Medium)

piles에 있는 돌들을 반틈하는 과정을 반복해서 최소한의 돌 개수를 반환하는 문제. 처음에는 그냥 간단하게 정렬하고 가장 맨 처음 돌을 반토막 내고 다시 정렬하는 방식으로 하면 될거라고 생각했으나 마찬가지로 Time Exceeded 문제에 맞닥드렸다.

class Solution:

    def find_max(self, piles):
        index = 0
        for i in range(len(piles)):
            if piles[i] > piles[index]:
                index = i
        return (index, piles[index]) 

    def minStoneSum(self, piles: List[int], k: int) -> int:
        import math
        total = sum(piles)
        piles.sort(reverse=True)
        while k > 0:
            half = math.floor(piles[0] / 2)
            total -= half
            piles[0] -= half
            k -= 1
            if len(piles) > 1 and piles[0] < piles[1]:
                piles.sort(reverse=True)
        return total

이러한 문제를 해결하는 방식은 Heap을 이용하는 것이다. 정말 오랜만에 들어보는 데이터구조인데, 학교에서 배웠긴 하지만 PS에 사용해본적이 없어서 까먹고 있었다. Heap을 이용한 풀이는 다음과 같다.

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        pq = [-x for x in piles]
        heapify(pq)
        for _ in range(k): heapreplace(pq, pq[0]//2)
        return -sum(pq)

음수로 변형한 이유는 floor을 좀더 빠르게 처리하기 위함이고 heapreplace 라는 함수를 이용해서 구현하였다.

1743. Restore the Array From Adjacent Pairs (Medium)

처음 구현한방식은 처음과 끝 값을 먼저 찾은 다음 연결하는 방식으로 생각했다. 그러나 늘 그렇듯이 time exceeded가 떠버리고, 다른 방식을 생각하는 중이다.

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        temp = {}
        for pair in adjacentPairs:
            temp[pair[0]] = temp.get(pair[0], 0) + 1
            temp[pair[1]] = temp.get(pair[1], 0) + 1
        keys = temp.keys()
        arr = []
        for key in keys:
            if temp[key] == 1:
                arr.append(key)
        end = arr.pop()
        while arr[-1] != end:
            for pair in adjacentPairs:
                if pair[0] == arr[-1]:
                    arr.append(pair[1])
                elif pair[1] == arr[-1]:
                    arr.append(pair[0])
        return arr

그러나 새로운 풀이를 보고서, 문제를 풀어나가는 방식에는 틀린점이 없다는 걸 알았다. 하단부분에 while문을 풀어나가는 방식에서 조금 차이점이 있을 뿐 다른 점은 거의 없었는데 이런 디테일한 부분을 고치기 위해서는 조금더 문제를 많이 경험해봐야 할 것 같다.

class Solution:
    def restoreArray(self, adjacent: List[List[int]]) -> List[int]:
        
        start_options = []
        g = collections.defaultdict(list)
        for a, b in adjacent:
            g[a].append(b)
            g[b].append(a)
            
        for num in g:
            if len(g[num]) == 1:
                start_options.append(num)
                
        res = [start_options[0]]
        used = set([start_options[0]])
        while True:
            for num in g[res[-1]]:
                if num not in used:
                    used.add(num)
                    res.append(num)
                    break
            else:
                return res

You may also enjoy