프로그래머스 - 요격 시스템

프로그래머스 - 요격 시스템

폭격 미사일들을 최소한의 비용으로 요격하는 문제입니다. 자세한 내용은 위의 링크를 참고하시기 바랍니다.

미사일들의 끝점을 기준으로 정렬합니다. 순서대로 읽어가며 현재 미사일을 기준으로 시작점이 현재 미사일의 끝점보다 앞에 있는 미사일들은 같이 요격할 수 있음을 알 수 있습니다. 끝점순으로 정렬했기 때문에 현재 미사일 뒤의 미사일들은 어차피 끝점이 더 뒤에 있습니다. 그러니까 현재 미사일의 끝점 쪽에서 한번에 요격할 수 있습니다. 이런 미사일들끼리 묶습니다.

근데 묶음이 끊기고 나서 더 뒤의 미사일 중 시작점이 현재 미사일의 끝점보다 앞에 있는 건 생각 안해도 될까요?

네. 그런 경우는 어차피 그보다 앞에 있는 미사일의 끝점이 현재 미사일의 끝점보다 뒤에 있기 때문에 거기서 묶입니다.

다음으로 이게 최소 비용인 이유는, 위의 방식으로 묶은 덩어리의 시작점들끼리 서로 disjoint해서 서로서로 한번에 요격할 수 없다는 것입니다. 덩어리의 시작점이라는 것은 위 설명 기준 현재 미사일, 아래 코드 기준 cur입니다. for문을 돌며 갱신되는 cur끼리는 어떤 쌍을 가져와도 한번에 요격이 불가능합니다. 이말은, 최종적으로 어떤 방식으로 요격에 성공해도 최소한 cur 개수만큼은 요격을 해야한다는 것입니다.

끝을 기준으로 정렬하는 아이디어는 다음 링크의 백준 문제 경험이 도움이 됐습니다. (링크 : 백준 - 회의실 배정) 그리디는 평범한 센스를 가진 사람 기준으로는 많이 풀어보는 수밖에 없는 것 같습니다.

여담으로 이 백준 문제는 제가 막 코딩을 시작했을때 2시간을 끙끙대다 못풀었는데, 프로그래밍과 관련없는 한 카이스트 대학원생이 20분만에 풀이법을 제시했습니다ㅠㅠ

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        Arrays.sort(targets, new Comparator<int[]>() {
            @Override
            public int compare(int[] target1, int[] target2) {
                return target1[1] - target2[1];
            }
        });
        
        int[] cur = new int[] {0, 0};
        
        for (int[] target : targets) {
            if (cur[1] > target[0]) {
                continue;
            }
            cur = target;
            answer++;
        }
        
        return answer;
    }
}