차량에 처음부터 승객을 태울 수 있는 빈 좌석이 capacity개 있다고 가정해 봅시다. 이 차량은 동쪽으로만 주행하기 때문에 방향을 바꿔 서쪽으로 되돌아갈 수 없습니다. 우리에게는 여행 정보 목록 trips가 주어지며, 각 여행은 trip[i] = [num_passengers, start_location, end_location] 형태로 표현됩니다. 즉, num_passengers는 태워야 할 승객 수를, start_location과 end_location은 승객을 태우고 내려주는 지점을 나타냅니다. 위치 값은 차량의 초기 위치에서 동쪽으로 몇 킬로미터 떨어져 있는지를 의미합니다.
모든 여행에 대해 승객을 제시간에 태우고 내려주는 것이 가능하다면 true를, 그렇지 않다면 false를 반환해야 합니다. 예를 들어 trips = [[2,1,5],[3,3,7]]이고 capacity = 5라면 출력은 true입니다.
해결 접근 방법
이 문제는 스위핑(Sweeping) 기법, 즉 지점별 변화량을 누적하는 방식으로 효율적으로 해결할 수 있습니다. 각 위치에서 승객 수가 얼마나 늘고 줄어드는지를 기록한 뒤, 출발 지점부터 순서대로 누적하면서 차량 정원을 초과하는 순간이 있는지만 확인하면 됩니다.
- 크기가 1001인 배열
stops를 만들고 모든 요소를 0으로 초기화합니다. trips의 각 여행i에 대해 다음을 수행합니다.stops[i[1]] += i[0]— 탑승 지점에서 승객 수만큼 증가stops[i[2]] -= i[0]— 하차 지점에서 승객 수만큼 감소
stops배열을 순서대로 순회하며 다음을 수행합니다.capacity -= i— 현재 지점까지의 누적 승객 수를 정원에서 차감- 만약
capacity < 0이면 정원을 초과한 것이므로false를 반환합니다.
- 모든 지점을 통과한 후에도
capacity >= 0이라면true를 반환합니다.
이 알고리즘의 시간 복잡도는 여행 수를 n, 최대 위치 값을 m이라 할 때 O(n + m)이며, 공간 복잡도는 O(m)입니다. 여행 개수와 무관하게 위치 범위에 비례하는 선형 시간에 해결할 수 있어 매우 효율적입니다.
예제 코드
class Solution(object): def carPooling(self, trips, capacity): stops = [0 for i in range(1001)] for i in trips: stops[i[1]]+=i[0] stops[i[2]]-=i[0] for i in stops: capacity-=i if capacity<0: return False return capacity>=0 ob = Solution() print(ob.carPooling([[2,1,5],[3,3,7]],5))
입력
[[2,1,5],[3,3,7]] 5
출력
True