프로그래머스: 단속카메라 [JAVA]

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42884

코딩테스트 연습 - 단속카메라

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 차량 정보(진입, 진출 지점)를 가지는 객체 생성
2. 해당 차량 정보에 대한 우선순위 큐 생성 (차량의 진입 시점이 빠를수록, 진출 시점이 빠를 수록)
3. routes 배열들 통해 순차적으로 차량 정보 객체 생성 후 우선순위 큐에 삽입
4. 한 번의 반복문을 통해 탐색 진행
   • 해당 탐색에서는 뽑힌 첫 차량의 진입, 진출을 구간의 시작, 끝으로 잡고, 이후 뽑은 차량의 진입, 진출 시점이 해당 구간에 속하는지, 속한다면 앞선 차량들이 모두 속할 수 있게 구간을 좁히고 아니면 함수를 종료
5. 한 번의 탐색이 끝나면 답에 1을 추가

  처음 문제를 보았을 때는 한 번의 카메라 위치 선택을 통해 얼마나 많은 차량을 커버할 수 있는 지에 대해서만 집중해 문제를 매우 어려워했다. 하지만 해당 방식으로는 도저히 방법이 보이지 않아 문제의 해결 방식을 다르게 생각해 문제를 풀 수 있었는데, 바로 하나의 차량을 커버하기 위한 카메라 설치 구간을 선택하고, 이후 해당 구간이 얼마나 많은 다른 차량들을 커버할 수 있는 지를 계산하는 거였다. 물론 이런 경우 차량 구간 양 옆으로 다른 구간이 겹쳐져 있으면 이를 계산하기가 어려워지지만, 만약 전체 도로의 시작이나 끝에 있는 차량을 1순위로 생각하면 그 다음 차량들만 고려하면 되어 계산이 편해진다.

 우선 차량 진입, 진출 정보를 담고 있는 객체를 생성하고 해당 객체들을 정렬할 수 있는 우선순위 큐를 생성한다. 이 때 우선순위큐의 적용될 방식은 차량의 진입이 빠를수록, 진입이 동일하다면 진출이 빠를수록 우선순위가 높게 지정한다. 이후에는 주어진 routes 배열을 돌며 순차대로 차량정보를 생성해 우선순위 큐에 넣어준다.

 그 다음으로는 한 번의 탐색을 통해 우선순위 큐에서 차량 정보들을 제거하는 데, 이 때 가장 먼저 나온 차량의 진입과 진출 시점을 구간의 시작과 끝으로 잡고 그 다음 차량을 뽑아 해당 차량의 진입이나 진출이 구간에 속하는 지를 계산한다. 만약 속하게 되면 현재 카메라 구간에서 다음 차량을 포함할 수 있는 구간이 존재한다는 뜻이므로, 다음 차량까지 포함할 수 있는 구간으로 수정한 후 다시 우선순위 큐에서 차량 정보를 뽑는 과정을 반복하는 것이다. 이렇게 되면 한 번의 탐색을 통해, 하나의 카메라를 통해 최대의 차량 정보를 제거할 수 있고, 탐색이 한 번 끝날 때마다 답에 1을 더해주면 최종적으로 몇 대의 카메라가 필요한 지를 알 수 있게 된다.

 

class Solution {
	PriorityQueue<CarMoveInfor> pq = new PriorityQueue<>();

    public int solution(int[][] routes) {
        int answer = 0;

        for (int i = 0; i < routes.length; i++) { //우선순위큐에 차량 정보 삽입
            pq.add(new CarMoveInfor(routes[i][0], routes[i][1]));
        }

        while (!pq.isEmpty()) {//한 번의 탐색 당 답+1
            checkSection();
            ++answer;
        }

        return answer;
    }

    void checkSection() { //한 번의 탐색
        CarMoveInfor firstCar = pq.poll();
        int sectionStart = firstCar.start, sectionEnd = firstCar.end; //가장 첫 차량의 구간

        while (!pq.isEmpty()) { //다음 차량이 구간에 포함이 되는 가능한지 확인
            CarMoveInfor car = pq.peek();
            int carStart = car.start, carEnd = car.end;

            //구간에 속한다면 앞선 차량들이 모두 포함되도록 구간을 좁힌다.
            if (sectionStart <= carStart && carStart <= sectionEnd || sectionStart <= carEnd && carEnd <= sectionEnd) {
                if (sectionStart <= carStart) {
                    sectionStart = carStart;
                }

                if (carEnd <= sectionEnd) {
                    sectionEnd = carEnd;
                }

                pq.poll();
            } else {
                return;
            }
        }
    }


    class CarMoveInfor implements Comparable<CarMoveInfor>{ //자동차의 진입, 진출 정보
        int start, end;

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

        @Override
        public int compareTo(CarMoveInfor o) {//정렬 (진입, 진출이 더 빠를수록 우선순위가 높게)
            if (this.start < o.start) {
                return -1;
            } else if (this.start == o.start) {
                if (this.end < o.end) {
                    return -1;
                } else {
                    return 1;
                }
            } else {
                return 1;
            }
        }
    }
}

결과