[프로그래머스] 요격 시스템

스케줄링과 비슷한 레벨 2의 요격 시스템 문제를 풀어보았다.

 

스케줄링 문제는 개념은 알고있었는데 관련 문제는 처음 풀어보는 것 같다.

import java.util.*;

// A나라의 미사일은 X축에 평행하게 좌표로 주어짐
// B나라에서 최소한의 미사일을 사용하여 요격
// 시간복잡도 O(N^2) <= O(X) <= O(NlogN)예상
// 스케줄링과 비슷해보임
class Solution {
    public int solution(int[][] targets) {
        
        // 선의 끝 x값이 작은 값부터 앞으로 오도록 정렬.
        // 만약 끝 x좌표가 같다면 앞 x좌표가 가까운 것이 오도록 정렬. 
        Arrays.sort(targets, (o1, o2) -> {
            if(o1[1] == o2[1]){
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });
        
        int count = 1;
        int end = targets[0][1];
        
        // 만약 현재 스케줄링의 위치로 해결할 수 없을 경우
        // 해당 선의 x좌표 끝값으로 재설정한 후 카운트 하나 증가
        for(int[] target : targets){
            if(end <= target[0]){
                end = target[1];
                count++;
            }
        }
        
        return count;
    }
}