[LeetCode] 1057. Campus Bikes

 Worker의 2차원 좌표를 담은 workers와 Bike의 2차원 좌표를 담은 bikes 리스트가 각각 주어지고, worker와 bike가 가장 가깝게 쌍을 지어주는 문제다. 문제를 복잡하게 생각해 Priority Queue(우선순위 큐)를 사용하기 위해 heapq를 사용했으나 오히려 사이즈가 큰 input은 TLE(Time Limit Exeeded)가 발생한다. 오히려 간단하게 거리를 계산한 모든 쌍을 리스트에 담고 리스트를 정렬해 거리가 짧은 순서부터 반환할 리스트에 담으면 쉽게 해결된다.

 아래는 앞서 말한 모든 쌍을 리스트에 담고 정렬한 솔루션인데 시간복잡도 측면에선 중복 체크를 리스트(bl) 대신 세트를 사용하면 훨씬 개선이 가능하다.

 참고로 가장 높은 vote를 받은 솔루션은 Bucket Sort를 사용했다.

 

class Solution:
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
        ret = [-1 for i in range(len(workers))]
        ds = []

        for i, w in enumerate(workers):
            for j, b in enumerate(bikes):
                d = abs(w[0] - b[0]) + abs(w[1] - b[1])
                ds.append([d, i, j])

        ds.sort()

        bl = []
        for i, item in enumerate(ds):
            if ret[item[1]] == -1 and item[2] not in bl:
                ret[item[1]] = item[2]
                bl.append(item[2])
        
        return ret