문제 해설

이런 문제 유형이 코딩 테스트로 자주 출제되는 것 같습니다.

뭔가 공통된 부분에 설치를 한다. 확인을 한다라는 포인트로 문제가 기출이 되면 힙으로 해결하면 됩니다.

자바에서는 우선 순위 큐로 해결이 가능합니다.

알고리즘 동작 순서

1. 모든 차량 운행 정보를 진입 지점 오름차순으로 정렬합니다. 동일한 경우는 진출 지점 오름차순으로 합니다.
2. 운행 정보 하나를 빼옵니다
   1. 카메라 개수 한 개 증가
   2. 가져온 운행 정보로 카메라를 설치할 수 있는 범위를 좁히면서 힙에서 하나씩 뽑아줍니다.
   3. 더 이상 뽑을 수 없다면 2번으로 다시 돌아갑니다.

이 문제에서는 2-2번이 포인트입니다.

운행 정보나 스트리밍 정보나 결국 겹치는 시간들이 존재하게 됩니다.

그럼 겹치는 범위를 좁혀가며 중복된 범위가 있는 운행 정보들을 날려주면 되겠죠.

이 문제의 경우 3가지 케이스가 있습니다.

케이스 1

cur : =======

nxt : =========

케이스 2

cur : ========

nxt : ====

케이스 3

cur : =========

nxt : ==========

범위를 좁혀가는 과정에서 케이스에 따라 다음에 맞춰볼 범위를 조정해야 합니다.

케이스 1번의 경우 cur 범위를 그대로 가져갑니다.

케이스 2번의 경우 next 범위를 가져갑니다.

케이스 3번의 경우 next의 진입과 cur 의 진출 시점을 범위로 가져갑니다.

이렇게 범위를 좁혀가면서 범위가 중복되는 차량 운행 정보를 한번에 최대한 제거하는 경우 카메라를 1개 설치하면 되겠죠.

이를 반복해서 해결하면 됩니다.

코드

package 프로그래머스;

import java.util.PriorityQueue;

public class 프로그래머스_단속카메라 {
    public int solution(int[][] routes) {

        PriorityQueue<Car> carQueue = new PriorityQueue<>();

        for (int[] car : routes) {
            carQueue.add(new Car(car[0], car[1]));
        }

        int camera = 0;

        while(!carQueue.isEmpty()) {
            Car cur = carQueue.peek();
            camera++;

            while (!carQueue.isEmpty()) {
                Car next = carQueue.peek();
                if (caseOne(cur, next)) {
                    cur = next;
                    carQueue.poll();
                } else if (caseTwo(cur, next)) {
                    cur = new Car(next.start, cur.end);
                    carQueue.poll();
                } else if (caseThree(cur, next)) {
                    carQueue.poll();
                }
                else
                    break;
            }

        }

        int answer = camera;
        return answer;
    }

    private boolean caseThree(Car cur, Car next) {
        return next.start <= cur.start && cur.end <= next.start;
    }

    private boolean caseTwo(Car cur, Car next) {
        return next.start <= cur.end && next.end > cur.end;
    }

    private boolean caseOne(Car cur, Car next) {
        return next.start <= cur.end && next.end <= cur.end;
    }

    class Car implements Comparable<Car>{
        int start;
        int end;

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

        @Override
        public int compareTo(Car o) {
            int startComp = Integer.compare(this.start, o.start);
            if (startComp == 0)
                return Integer.compare(this.end, o.end);
            return startComp;
        }

        @Override
        public String toString() {
            return "Car{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }

    public static void main(String[] args) {
        new 프로그래머스_단속카메라().solution(new int[][]{{-20,15}, {-14,-5}, {-18,-13}, {-5,-3}});
    }
}