Lv.3 단속카메라

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

프로그래머스

1차원 int[] 배열을 요소로 갖는 2차원 int[][] 배열은 Arrays.sort로 정렬할때

매개변수로 익명 comparable 구현 객체(람다)를 사용할 수 있다는걸 깜빡하고 정렬을 우선순위 큐로 했다.

기본 타입인 int 타입을 요소로 갖는 1차원 int[] 배열을 정렬할 경우엔 사용이 불가한데 이점과 헷갈렸다.

그리고 범위를 저장할 필요없이 진출 지점만 저장해놓고 비교해보면 되는데 배열을 사용했다.

이 부분 또한 개선해야겠다.

// 기존 코드
import java.util.PriorityQueue;

class Solution {
    public int solution(int[][] routes) {
        int cnt = 1;
        PriorityQueue<int[]> pq = new PriorityQueue<>((arr1, arr2) -> arr1[0] - arr2[0]);
        for (int[] route : routes) {
            pq.add(route);
        }
        int[] route = pq.poll();
        
        while (!pq.isEmpty()) {
            int[] nextRoute = pq.poll();
            if (route[1] < nextRoute[0]) {
                route = nextRoute;
                cnt++;
                continue;
            }
            route[0] = nextRoute[0];
            route[1] = Math.min(route[1], nextRoute[1]);
        }
     
        return cnt;
    }
}

// 개선 코드
import java.util.Arrays;

class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (arr1, arr2) -> arr1[0] - arr2[0]); // 진입 지점이 빠른순으로 정렬
        int cnt = 1; // 차량 대수는 1대 이상이므로 카메라 1대는 반드시 세워진다고 보고 두번째 차량부터 확인할 것이다.
        int outPoint = routes[0][1]; // 첫번째 차량의 진출 지점이자 카메라가 기존 차량들을 커버할 수 있으면서 설치 가능한 최대 지점
        
        for (int i = 1; i < routes.length; i++) { // 2번째 ~ 마지막 차량을 확인
            int[] nextRoute = routes[i]; // 다음 차량의 진입, 진출 지점
            if (outPoint < nextRoute[0]) { // 다음 차량이 기존 카메라의 최대 설치 지점보다 먼 곳에서 진입하면 true
                outPoint = nextRoute[1]; // 카메라를 한대 더 세우고 카메라의 최대 설치 지점을 갱신한다.
                cnt++; // 카메라 대수 증가
                continue; // 다음 차량을 확인
            }
            // 다음 차량이 세워둔 카메라로 커버되는 경우
            if (outPoint > nextRoute[1]) { // 다음 차량의 진출 지점이 카메라의 커버 범위보다 작다면 true
                outPoint = nextRoute[1]; // 현재 카메라의 최대 설치 지점을 다음 차량의 진출 지점으로 갱신한다.
            }
        }
     
        return cnt; // 카메라 대수 return
    }
}