[Leetcode] Car Pooling

leetcode.com/problems/car-pooling/

Car Pooling - LeetCode

여행 동선과 승객들이 주어졌을 때, 한 차로 카풀이 가능한지 안한지를 판단하는 문제이다.

아래와 같은 제약조건이 주어지는데, 보시다시피 그냥 막 소팅하고 다 검색해도 Pass는 된다.

Constraints: trips.length <= 1000 trips[i].length == 3 1 <= trips[i][0] <= 100 0 <= trips[i][1] < trips[i][2] <= 1000 1 <= capacity <= 100000

 

 

 

좀 더 최적화는 가능하겠지만 전형적인 Greedy 방식으로 풀었다.

시간 순서로 소팅 후 시간 별로 passentger 수를 추가해주다가 capacity를 넘는 순간이 있으면 false를 리턴하도록.

public static boolean carPooling2(int[][] trips, int capacity) {
    Arrays.sort(trips, CarPooling::compare);
    int[] passengers = new int[MAX];
    for (int now = 0; now < trips.length; now++) {
        for (int l = trips[now][START]; l < trips[now][END]; l++) {
            passengers[l] += trips[now][PASSENGERS];
            if(passengers[l] > capacity) return false;
        }
    }
    return true;
}
private static int compare(int[] a, int[] b) {
    if ((a[1] > b[1]) || (a[1] == b[1] && a[2] > b[2])) {
        return 1;
    }
    return -1;
}

 

위 코드는 O(N^2) 시간이 걸린다. 전체 trips 수만큼 돌면서 한 trip당 최악의 경우는 전체 시간을 돌아야 하기 때문이다.

 

최적화 포인트는 두가지가 있다.

SORT 하는 부분과 실제 Car Pooling 가능한지 판단하는 부분.

 

아래처럼 최적화가 가능하다.

public boolean carPooling3(int[][] trips, int capacity) {
    Map<Integer, Integer> passengers =  new TreeMap<>();
    for (int[] trip : trips) {
        passengers.put(trip[START], passengers.getOrDefault(trip[START], 0) + trip[PASSENGERS]);
        passengers.put(trip[END], passengers.getOrDefault(trip[END], 0) - trip[PASSENGERS]);
    }
    int nowCapacity = 0;
    for (int cap : passengers.values()) {
      nowCapacity += cap;
      if (nowCapacity > capacity) return false;
    }
    return true;
}

TreeMap은 SortedMap을 상속받았기 때문에 자동 정렬되면서 put을 한다. 

이 코드는 O(N * log N) 이다. 

Sort 하는 부분은 첫 코드와 차이는 없지만, 실제 passenger들이 capacity를 넘었는지 판단하는 부분은 O(N)이면 끝난다.

 

여기서 드는 의문이 왜 sort가 필요한가?

sort 없이 하는 방법은 배열 indexing으로 처리하는 방식이니까

 

실제 Car Pooling 길을 어느 길에서 몇명을 태우고 어느 길에서 몇명을 내려주는지 한번 훑어본 후

가능한지 불가능한지만 판단해주면 된다. 

완전 문제 그대로인데 생각하긴 어려웠음 끄읏

public boolean carPooling(int[][] trips, int capacity) {
    int[] passengers =  new int[MAX];
    for (int[] trip : trips) {
        passengers[trip[START]] += trip[PASSENGERS];
        passengers[trip[END]] -= trip[PASSENGERS];
    }
    int nowCapacity = 0;
    for (int cap : passengers) {
        nowCapacity += cap;
        if (nowCapacity > capacity) return false;
    }
    return true;
}