Car Pooling [leetcode]

문제

1094. Car Pooling

Medium

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Constraints:

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengersi <= 100
• 0 <= fromi < toi <= 1000
• 1 <= capacity <= 105

코드

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        temp = [0] * 1000
        for trip in trips:
            psg = trip[0]
            start = trip[1]
            end = trip[2]
            for idx in range(start-1,end-1):
                temp[idx] += psg
          
        if(max(temp)> capacity):
            return False
        else:
            return True

문제 풀이

각 배열값으로는 [승객수, 시작정류장, 내릴정류장] 이 들어온다.

차는 왼쪽에서 오른쪽으로 증가만 하며 [1→1000] 진행한다.

각 정류장 별로 승객이 차 용량보다 많이 타야 된다면 (capacity를 넘는다면)

false, 그렇지 않다면 진행이 가능하므로 true값을 반환하는 검증 로직이다.

첫번째 접근

일단, 시작 정류장이 빠른순으로 sort를 해줬다. (힌트 보기전에 sort 부터 했는데, 힌트도 sort 하라고했음)

sort_trips = sorted(trips, key = lambda x : x[1])

해당 sort_trips 를 loop를 돌면서 순회를 하려고 보니 문제가 되는 지점이 있었다.

다음 순서때 시작 정류장은 이전 정류장 사이에 존재하는 값인지 검증이 필요한것이다.

바로 다음만 검증한다면 문제될건 없지만 만약 다음 데이터로 [4,2,4] 같은 값이 들어온다면 해당 값까지 검증...

결국 어떤 값이 들어올지 알 수 없기 때문에 이전 정류장 구간에 포함되는지 전부 검사해야 한다는 문제가 생긴다.

두번째 접근

그렇다면 for loop (1~1000)까지 돌리면 어떨까? (각 정류장을 미리 세워놓는 것같이)

해당 로직의 문제는 첫번째 접근과 마찬가지로 문제점이 있다.

for n in range(1,1001):
    # n == 1 일때 start가 1인 값을 배열에서 찾아야 함
    for trip in trips:
        if trip[1] == n: #이 얼마나 비효율적인지...

각 정류장 숫자별로 해당 값이 존재하는지 배열을 전부 뒤져야 하는 문제가 발생한다.

세번째 접근

이건 sort도, 정류장별로 뒤지지도 않는다.

시작-종료 구간은 최대 1000이라고 문제 조건에 나와있다. 그렇다면 각 정류장 구간에 승객수를 채운다면?

temp = [0] * 1000 #정류장은 최대 1000개
for trip in trips:
    psg = trip[0]
    start = trip[1]
    end = trip[2]
    for idx in range(start-1,end-1):# 각 정류장 구간에 승객을 채운다.
        temp[idx] += psg

위 로직대로면 어느 구간에서도 capacity를 넘지 않는다면 → true!! 그렇지 않다면→ false!!

if(max(temp)> capacity):
    return False
else:
    return True

게다가 sort도 필요하지 않다!!

퇴근하면서 지하철에서 해당 방법이 생각나서 못참고 그만

핸드폰으로 풀고 말았다.

 

문제링크는 여기

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

Car Pooling - LeetCode