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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=java# 

프로그래머스

 

필요한 개념

• 정렬 또는 우선순위 큐 사용

풀이

로직은 다음과 같다.

1. 우선순위 큐에서 첫번쨰로 뽑은 것을 카메라를 설치한다.
2. 현재 카메라가 설치되는 가장 오른쪽 범위보다 작아지면, 카메라 위치를 갱신한다. 
3. 현재 카메라보다 들어오는 위치가 크면, 카메라 개수를 1더하고, 카메라 위치를 갱신한다. 

현재 카메라 보다 작은 숫자가 들어오는 반례를 생각못해, 애좀 먹었다. 

참고

우선순위 큐 정렬은 들어오는 위치가 같으면 더 빨리 나간 순, 그게 아니면 오름차순 정렬을 한다.

코드

자바

import java.util.*;

class Solution {
    //[in, out]
    public int solution(int[][] r) {
        int answer = 1;
        //{들어감, 나감}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]==0 ? a[1]-b[1] : a[0]-b[0]);
        
        for(int x[] : r){
            int a = Math.max(x[0], x[1]);
            int b = Math.min(x[0], x[1]);
            pq.offer(new int[]{b,a});
        }
        int cameraFin  = pq.poll()[1];
        
        while(!pq.isEmpty()){
            int[] c = pq.poll();
            if(c[0] > cameraFin){
                cameraFin = c[1];
                answer++;
            }else if(c[1] < cameraFin){
                cameraFin = c[1];
            }
        }
        return answer;
    }
}