문제 설명

수평선 위에 각 자동차들이 존재하는 시작점과 끝점이 배열로 주어진다.
모든 자동차들이 최소한 한 번씩 지나갈 수 있도록 수직선 위에 단속카메라를 세운다고 생각해보자.
이떄, 최소 몇개를 세워야 하는가?

문제 접근

우선, A라는 자동차가 끝나면 그 뒤에 아무리 카메라를 설치해도 의미없는 행위가 된다. A는 통과하지 못함. 따라서, 자동차가 끝나는 지점을 기준으로 오름차순 정렬을 한다.
그리고, 먼저 끝나는 자동차의 끝지점에다가 카메라를 설치한다. 그리고 다음으로 끝나는 자동차들을 마저 순회하면서 만약 이미 카메라 설치 지점을 지났는지를 파악해야 한다.
=> 이게 사실 제일 중요한 관건이다. 이걸 해결하지 못하면 6만*1만 이상의 시간 복잡도를 갖게 된다.
이를 해결하기 위해, 먼저 출발하는 순서로도 정렬된 배열을 유지하면 된다.
이렇게 되면 끝나는 자동차를 기준으로 먼저 카메라를 설치하고, 이번에 설치한 카메라의 위치를 기준으로, 먼저 출발하는 자동차 배열에서 아직 해결하지못한 인덱스의 자동차부터 이번에 설치한 카메라를 지나는지 확인한다. 해결됐다면 해결됐다고 자동차에 체크를 해주면 된다.
그러면, 다음에 끝나는 자동차를 확인할 때 이미 해결된 경우면 무시하면 된다.

문제 풀이

import java.util.*;

class Solution {
    ArrayList<Car> firstEnd = new ArrayList();
    ArrayList<Car> firstStart = new ArrayList();    
    public int solution(int[][] routes) {
        int answer = 0;
        for(int i = 0; i<routes.length; i++) {
            Car c = new Car(i, routes[i][0], routes[i][1]);
            firstEnd.add(c);
            firstStart.add(c);
        }
        
        firstEnd.sort((c1,c2)->{ return c1.e - c2.e; });
        firstStart.sort((c1,c2)->{ return c1.s - c2.s; });
        
        int sP = 0;
        for(Car c: firstEnd) {
            if(c.isSolved) continue;
            int turnPoint = c.e;
            c.isSolved = true;
            answer++;
            for(int i=sP; i<firstStart.size(); i++) {
                if((firstStart.get(i).e >= turnPoint && firstStart.get(i).s <=turnPoint)) {
                    firstStart.get(i).isSolved = true;
                } else {
                    sP = i;
                    break;
                }
            }
        }
            
        return answer;
    }
    
    
}

class Car {
    final int num;
    final int s;
    final int e;
    boolean isSolved = false;
    Car(int num, int s, int e){
        this.num = num;
        this.s = s;
        this.e = e;
    }
}

2024년 5월 22일 다시 풀어보았다.

훨씬 더 코드가 쉬워진 것 같다. 우선, 끝나는 순으로 정렬하고 시작순으로 정렬해서, 끝나는 순 기준으로 아직 해결안됐다면 그 끝종료지점에 단속카메라를 설치한다. 그리고 시작하도록 정렬한 배열에서 마지막으로 봤던 곳 이후부터 다시 이 단속카메라로 감시가 되는 카메라들을 체크해나간다.

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        ArrayList<Car> endOrders = new ArrayList();
        ArrayList<Car> startOrders = new ArrayList();

        for(int i=0; i<routes.length; i++) {
            Car car = new Car(routes[i][0], routes[i][1]);
            endOrders.add(car);
            startOrders.add(car);
        }
        Collections.sort(endOrders, (c1,c2) -> {
            return c1.e-c2.e;
        });
        
        Collections.sort(startOrders, (c1,c2) -> {
            return c1.s-c2.s;
        });
        
        int j=0;
        for(int i=0;i<endOrders.size(); i++) {
            Car car = endOrders.get(i);
            if (car.pass) continue;
            car.pass = true;
            answer++;
            for(;j<startOrders.size(); j++) {
                Car sCar = startOrders.get(j);
                if (sCar.s <= car.e && sCar.e >= car.e) {
                    sCar.pass = true;
                } else break;
            }
        }
        
        return answer;
    }
}

class Car {
    int s;
    int e;
    boolean pass = false;
    Car(int s, int e) {
        this.s = s;
        this.e = e;
    }
}