[프로그래머스/Greedy] Level 3 단속카메라 (JAVA)

문제

---

풀이

1차 시도: 카메라 구간 저장

1. cars 배열을 차가 도로에 입장하는(cars[i][0]) 순서대로 오름차순으로 정렬한다.
2. Camera 클래스에는 카메라가 촬영할 수 있는 최대 범위를 저장한다.
3. cars 배열을 차례대로 탐색하며, car가 모든 카메라의 범위 밖에 있으면 새 카메라를 추가한다.

import java.util.*;

class Solution {
    
    private static final int ENTER = 0;
    private static final int EXIT = 1;

    public int solution(int[][] cars) {
        Arrays.sort(cars, Comparator.comparingInt(car -> car[ENTER]));
        Set<Camera> cameras = new HashSet<>();
        for (int[] car : cars)
            if (cameras.isEmpty() || !isAnyCameraAvailableForCar(cameras, car))
                cameras.add(new Camera(car[ENTER], car[EXIT]));
        return cameras.size();
    }

    private boolean isAnyCameraAvailableForCar(Set<Camera> cameras, int[] car) {
        for (Camera camera : cameras) {
            if (camera.canCapture(car)) {
                camera.adjustRange(car);
                return true;
            }
        }
        return false;
    }
}

class Camera {
    int start;
    int end;

    public Camera(int start, int end) {
        this.start = start;
        this.end = end;
    }

    public boolean canCapture(int[] car) {
        return car[0] <= this.end;
    }

    public void adjustRange(int[] car) {
        this.start = Math.max(this.start, car[0]);
        this.end = Math.min(this.end, car[1]);
    }
}

아쉽게도 결과는 90점으로, 효율성 테스트에서 테스트케이스 4번 하나가 걸렸다.

아무래도 예외적인 경우가 효율성에서 걸리는 것 같아서 무엇이 문제일지 고민해보았다. 차량이 최대 1만대까지 주어진다고 했으니 내 코드대로라면 최악의 경우 1억번 탐색을 하게 된다. 이를 해결하기 위해서 아예 O(N)의 시간복잡도로 줄이던지, 아니면 한 번 탐색할 때 소요되는 시간을 줄이던지 해야겠다고 생각이 들었다.

정답: 설치 지점만 저장

그래서 카메라 탐색을 할 때 객체 말고 숫자값을 탐색하게 하려고 카메라 범위가 아니라 설치 지점을 저장하는 방식으로 개선했다. 그러기 위해 차가 도로에 입장하는 car[i][0]이 아닌, 탈출하는 시점인 car[i][1]을 카메라 설치 포인트로 잡았다. 탈출하기 전에만 카메라를 만나면 되니까 가장 먼저 탈출하는 차의 가장 마지막 순간에 카메라를 설치하고, 다음 차량들 중에 그 카메라를 지나치지 않는 차가 있으면 카메라를 추가로 설치하는 것이다.

import java.util.*;

class Solution {
    
    private static final int ENTER = 0;
    private static final int EXIT = 1;

    public int solution(int[][] cars) {
        Arrays.sort(cars, Comparator.comparingInt(car -> car[EXIT]));
        Set<Integer> cameras = new HashSet<>();
        for (int[] car : cars)
            if (cameras.isEmpty() || !isAnyCameraAvailableForCar(cameras, car))
                cameras.add(car[EXIT]);
        return cameras.size();
    }

    private boolean isAnyCameraAvailableForCar(Set<Integer> cameras, int[] car) {
        for (Integer camera : cameras)
            if (car[ENTER] <= camera && car[EXIT] >= camera)
                return true;
        return false;
    }
}

이렇게 풀었더니 효율성검사도 모두 통과하여 정답을 얻을 수 있었다.

정답: 하나의 카메라만 저장

근데 어차피 차량이 car[i][1]에 따라 오름차순으로 정렬되어 있으니 마지막에 설치한 카메라만 저장하면 된다는 생각이 들었다. 그래서 Set에 모든 카메라를 저장했던 것을 가장 마지막에 설치한 카메라 포인트 & 카메라 대수를 저장하는 방식으로 바꿨다.

import java.util.*;

class Solution {
    
    private static final int ENTER = 0;
    private static final int EXIT = 1;

    public int solution(int[][] cars) {
        Arrays.sort(cars, Comparator.comparingInt(car -> car[EXIT]));
        int camera = Integer.MIN_VALUE, count = 0;
        for (int[] car : cars)
            if (car[ENTER] > camera || car[EXIT] < camera) {
                camera = car[EXIT];
                count++;
            }
        return count;
    }
}

이렇게 최종적으로 O(N)의 시간복잡도로 문제를 풀 수 있었다. 와아~