[프로그래머스] level2 181188 - 요격 시스템(Java)

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

접근 방법

e를 기준으로 오름차순 정렬을 시키며, 앞에서부터 차례대로 검사한다.

미사일의 끝점을 기준으로 정렬시켜 해당 미사일이 커버가능한 시작점을 찾는 원리다.

위의 사진은 각 미사일을 끝점을 기준으로 오름차순 정렬시킨 그림과 유사하다.(3,7)와 (4,8)의 순서만 바꾸면 완벽이 정렬된 상태이다.

1. 처음 요격기의 값을 0으로 초기화한다.
2. 끝점으로 오름차순 정렬된 미사일의 시작점을 요격기의 값과 비교한다.
   2-1. 미사일의 시작점 값이 요격기 값 이상일 때, 요격기의 값을 해당 미사일의 끝점으로 업데이트 시키고 요격기의 개수를 추가한다.
3. 미사일 개수만큼 2의 과정을 반복한다.

개구간이므로 다음 미사일의 시작점이 before 값 이상이라면 미사일을 하나 추가한다.
(폐구간이라면 초과일 때만)

소스 코드

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        Arrays.sort(targets, (o1, o2) -> o1[1] - o2[1]);
        
        int before = 0;
        for(int i=0;i<targets.length;i++){
            if(before <= targets[i][0]){
                before = targets[i][1];
                answer++;
            }
        }
        
        return answer;
    }
}