[leetcode] 1094. Car Pooling

문제 : https://leetcode.com/problems/car-pooling/

---

총 좌석이 capacity인 차량이 있다. 차량엔 capacity 만큼의 탑승자만 태울 수 있다.

차량은 동쪽으로만 주행하며 (탑승자 수, from, to) 정보를 저장한 trip 배열이 주어진다. from에서 탑승자 수 만큼 차량에 태우고 to에 탑승자 수 만큼 차량에서 내린다. capacity를 넘지 않게 모든 trip 여행들을 탐색할 수 있으면 true 아니면 false를 반환하라.

---

부분합 배열을 만들어서 풀 수 있다. 

to의 최대값이 1000이므로 1000 크기의 passenger 배열을 만든다.

trips 배열을 탐색하며 passenger[from] 에는 탑승자 수 만큼 더하고, passenger[to]에는 탑승자 수를 빼준다.

그리고 passenger 배열을 처음부터 끝까지 탐색하며 passenger[i] += passenger[i-1] 을 하면서 실제로 탑승한 명수를 구한다.

만약 어떤 위치에서 실제 탑승자 수가 capacity를 넘는다면 false, 모든 위치에서 실 탑승자 수가 capacity를 넘지 않는다면 true를 반환한다.

 

시간/공간 복잡도는 O(N). N = |to|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1094.%20Car%20Pooling.cpp