Daniel's blog

다른 함수들은 모두 간단히 구현이 가능하지만 top을 어떻게 구현하느냐에 따라 효율이 달라진다. list를 heap로 구성하는 heapify를 통해 max heap을 구현후 하나씩 pop하는 방식을 활용해 K개의 가장 높은 점수를 더해 반환했다. import heapq class Leaderboard: def __init__(self): self.dic = defaultdict(int) def addScore(self, playerId: int, score: int) -> None: self.dic[playerId] += score def top(self, K: int) -> int: ret = 0 values = list(self.dic.values()) n_values = [-val for val i..

integer로 구성된 sticks라는 input array의 모든 요소를 이어 붙이는 문제다. 이 때 더할 때 마다 발생하는 합이 최소가 되도록 하는 문제다. sorting을 통해 풀이를 해야하나 잠시 생각했지만 Min heap을 사용하면 쉽게 구현이 가능하다. class Solution: def connectSticks(self, sticks: List[int]) -> int: mh = sticks ret = 0 heapify(mh) while len(mh) > 1: m1 = heappop(mh) m2 = heappop(mh) sum_ = m1 + m2 ret += sum_ heappush(mh, sum_) return ret

Worker의 2차원 좌표를 담은 workers와 Bike의 2차원 좌표를 담은 bikes 리스트가 각각 주어지고, worker와 bike가 가장 가깝게 쌍을 지어주는 문제다. 문제를 복잡하게 생각해 Priority Queue(우선순위 큐)를 사용하기 위해 heapq를 사용했으나 오히려 사이즈가 큰 input은 TLE(Time Limit Exeeded)가 발생한다. 오히려 간단하게 거리를 계산한 모든 쌍을 리스트에 담고 리스트를 정렬해 거리가 짧은 순서부터 반환할 리스트에 담으면 쉽게 해결된다. 아래는 앞서 말한 모든 쌍을 리스트에 담고 정렬한 솔루션인데 시간복잡도 측면에선 중복 체크를 리스트(bl) 대신 세트를 사용하면 훨씬 개선이 가능하다. 참고로 가장 높은 vote를 받은 솔루션은 Bucket So..