단속카메라

문제

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

코드

import java.util.*;

class Solution {

    class Node implements Comparable<Node>{
        int s;
        int e;

        public Node(int s, int e){
            this.s = s;
            this.e = e;
        }

        public int compareTo(Node obj){
            if(this.s < obj.s)
                return -1;
            else if(this.s > obj.s)
                return 1;
            else 
                return 0;
        }

    }

    public int solution(int[][] routes) {
        int answer = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(int[] route : routes){
            pq.add(new Node(route[0], route[1]));
        }

        Node cur_node = pq.poll();
        int threshold = cur_node.e;

        while(!pq.isEmpty()){
            cur_node = pq.poll();
            if(cur_node.s > threshold){
                threshold = cur_node.e;
                answer++;
            }else
                threshold = Math.min(threshold, cur_node.e);
        }

        answer++;

        return answer;
    }
}

피드백

• 나의 아이디어는 다음과 같다.
  • 진입시간 순으로 정렬을 한 뒤, 각 원소의 진출시간을 좁혀 더 이상 이 후의 원소를 현 그룹에 넣을 수 없을 때, 그룹을 나눈다.
• 왜 이 아이디어가 정답일까?
  • 생각해보면, 결국 그룹을 나누는 기준은 현 그룹 중 제일 빠른 진출 시간을 가지는 원소이다.
  • 즉 각 그룹의 기준 원소는, 서로 만나지 못하는 원소들이다.
  • 이 기준 원소의 갯수를 최소화 하도록 그룹을 나누는 것이, 이 문제의 최적해를 찾아가는 기본 방법이라고 할 수 있다.
  • 따라서 최대한 원소를 많이 중첩시키면서 그 임계값을 좁혀나가는 방법이 답이었다고 생각해 볼 수 있다.