각 행이 [start_x, end_x, num_passengers] 형태로 구성된 requested_trips라는 행렬이 있다고 가정해 보겠습니다. 각 요청된 여행은 start_x 위치에서 num_passengers명의 승객을 태워 end_x 위치에서 내려주는 것을 의미합니다. 또한 주어진 용량(capacity)만큼 승객을 수용할 수 있는 차량이 있으며, 이 차량은 x = 0 위치에서 출발합니다. 차량은 오른쪽 방향으로만 이동할 수 있으며, 우리는 모든 승객을 태우고 내려주어야 합니다. 이때 모든 승객을 성공적으로 태우고 내릴 수 있는지 확인해야 합니다.
예를 들어 입력이 trips = [[1, 25, 2], [3, 4, 3], [5, 12, 3]]이고 capacity = 6이라면, 출력은 True가 됩니다.
해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다 −
events라는 새로운 리스트를 생성합니다
trips의 각 (sx, ex, np) 집합에 대해 다음을 수행합니다
(sx, np) 쌍을 events 리스트 끝에 추가합니다
(ex, -np) 쌍을 events 리스트 끝에 추가합니다
carrying := 0으로 초기화합니다
정렬된 events 리스트의 각 (loc, delta) 쌍에 대해 다음을 수행합니다
carrying := carrying + delta
만약 carrying > capacity라면 False를 반환합니다
True를 반환합니다
동작 원리
이 알고리즘은 이벤트 기반 시뮬레이션 기법을 활용합니다. 각 여행을 '승차 이벤트(+승객 수)'와 '하차 이벤트(-승객 수)' 두 개의 이벤트로 변환한 뒤, 위치 기준으로 정렬하여 순서대로 처리합니다. 정렬 시 하차 이벤트의 델타 값이 음수이므로 같은 위치에서는 하차가 승차보다 먼저 처리되어, 내린 자리에 새 승객을 태울 수 있습니다. 이벤트를 처리하면서 현재 차량에 탑승 중인 승객 수(carrying)를 누적 계산하고, 어느 시점에서라도 용량을 초과하면 False를 반환합니다. 모든 이벤트를 통과했다면 True를 반환합니다. 시간 복잡도는 O(n log n)으로, n은 여행의 개수입니다.
더 나은 이해를 위해 다음 구현을 살펴보겠습니다 −
예제
class Solution:
def solve(self, trips, capacity):
events = []
for sx, ex, np in trips:
events.append((sx, np))
events.append((ex, -np))
carrying = 0
for loc, delta in sorted(events):
carrying += delta
if carrying > capacity:
return False
return True
ob = Solution()
trips = [
[1, 25, 2],
[3, 4, 3],
[5, 12, 3]
]
capacity = 6
print(ob.solve(trips, capacity))
입력
trips = [
[1, 25, 2],
[3, 4, 3],
[5, 12, 3] ]
capacity = 6
출력
True