단속 카메라

문제정의

---

최대한 많은 overlap을 하나로 묶을 때, 나오는 집합의 크기를 구하는 문제이다. 상세한 설명은 아래에 계속하겠다. 문제 링크

문제풀이

---

전체 코드는 다음과 같다.

import java.util.*;

class Section implements Comparable<Section>{
    int s;
    int e;
    public Section(int s, int e){
        super();
        this.s = s;
        this.e = e;
    }
    @Override
    public int compareTo(Section sec){
        return this.s - sec.s;
    }

}


public class SpeedTrap {
    
    //프로그래머스 level3 단속카메라
    public static void main(String[] args) {
        int[][] routes = {
            {-20, 15},
            {-14, -5},
            {-18, -13},
            {-5, -3}
        };

        PriorityQueue<Section> pq = new PriorityQueue<>();

        for(int i = 0; i < routes.length; i++)
            pq.add(new Section(routes[i][0], routes[i][1]));

        int cam_cnt = 0;
        while(!pq.isEmpty())
        {
            int end = pq.peek().e;
            while(!pq.isEmpty() && pq.peek().s <= end)
            {
                end = pq.peek().e < end ? pq.peek().e : end;
                pq.poll();
            }
            cam_cnt++;
        }

        System.out.println(cam_cnt);
    }
}

알고리즘의 이해를 돕기 위해 아래의 그림을 보자

프로그래머스에서 주어진 구간을 수평선 상에 표시하였다. 최소한의 카메라를 설치해야한다는 것은 최대한 차가 많이 다닐 것 같은 길목에 카메라를 놓아야 한다는 것이다. 그 말은 구간이 최대한 많이 겹치는 쪽에 카메라를 놓으면 된다는 것이다.

이를 구현하기 위해서 Section클래스를 선언하였다. 구간의 처음과 끝을 저장해두며, 정렬을 할 때 구간의 시작점을 기준으로 정렬한다.

우선순위 큐를 선언하여 Section을 집어넣는다. 이 큐에서 하나씩 빼면서 최대한 겹칠 수 있는 구간들을 묶을 것이다. 일단 end를 큐의 첫원소의 도착구간으로 설정한다. 그리고 end보다 출발점이 작은 구간은 무조건 겹치므로 이들을 팝한다. 이 때, 팝한 것들 중에 기존 end보다 작은 종료구간이 있다면 그 값으로 대체한다.

이 반복이 마치면 더 이상 겹치는 구간이 없다는 의미이므로 하나로 묶는 작업이 끝난 것이다. 카메라를 설치한다는 의미로 cam_cnt를 1가한다.

우선순위 큐를 사용하였기 때문에 구간의 개수를 n이라 하였을 때, 최종 시간복잡도는 $O(nlogn)$이다.

테스트

학교 수업에서 해봤던 문제라 수월하게 풀 수 있었다. 앞으로 나만의 코테 데이터베이스를 더 쌓아나가야지.