그리디 + 2차원배열 정렬 (PRO 단속카메라)

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

 

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        
        // 진출 지점을 기준으로 오름차순 정렬하기
        Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1]));
        
        int answer = 1;
        int currentCam = routes[0][1];
        
        for (int i = 1; i < routes.length; i++) {
            // "직전에 설치된 카메라 좌표 < 해당 요소의 진입 지점"인 경우, 새로운 카메라 설치 필요
            if (currentCam < routes[i][0]) {
                answer++;
                currentCam = routes[i][1];
                // "현재 카메라를 설치하는 최적 지점(=진출 지점)" 
                // = "전체 카메라 개수를 최소로 하는 지점"이므로, 그리디 문제임을 알 수 있다.
            }
        }
        return answer;
        
    }
}

 

이 코드의 주요 특징과 최적화 포인트는 다음과 같습니다:

1. 그리디 알고리즘 사용:
   - 진출 지점을 기준으로 차량 경로를 정렬하고, 최소한의 카메라로 모든 차량을 커버하는 방식을 사용합니다.
   - 이는 문제를 최적의 부분 해로 나누어 해결하는 그리디 접근법입니다.

2. 효율적인 정렬:
   - `Arrays.sort`와 람다 표현식을 사용하여 2차원 배열을 진출 지점 기준으로 정렬합니다.
   - 이는 O(n log n)의 시간 복잡도를 가집니다.

이 코드는 이미 매우 효율적이며, 대부분의 상황에서 최적의 성능을 제공할 것입니다.