[181188] 요격 시스템

✔ 요격 시스템

[프로그래머스 181188]

문제 분석하기

시작 좌표와 끝 좌표에서는 요격할 수 없으므로 그 사이의 좌표를 증가시키며 다른 좌표까지 같이 요격할 수 있는지 확인하도록 함

같이 요격할 수 없다면 미사일의 개수를 증가시키도록 함

손으로 풀어보기

1. 요격이 끝나는 시간인 e, 요격이 시작되는 시간인 s를 기준으로 정렬
2. 하나의 미사일이 여러 미사일을 요격하기 위해 미사일의 위치를 끝나는 시간으로 설정하고
   다른 미사일도 함께 요격할 수 있는지 확인
3. 함께 요격할 수 없는 미사일이라면 미사일을 하나 추가하고 위를 반복

슈도코드 작성하기

targets(각 폭격 미사일의 x 좌표 범위 목록)
answer(모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수)
e를 기준으로 오름차순 정렬, 같을 경우 s를 기준으로 정렬
end(요격 미사일의 위치) = targets[0][1]
answer 증가
for(target -> targets만큼) {
    if(target의 s가 end보다 크거나 같다면) {
        같이 요격하지 못하므로 미사일을 추가해야 하므로 answer 증가
        end를 target[1]로 갱신
    }
}
answer 반환

코드 구현하기

/**
 * 181188) 요격_시스템
 */
public class L105_181188 {
    // targets(각 폭격 미사일의 x 좌표 범위 목록)
    public int solution(int[][] targets) {
        // answer(모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수)
        int answer = 0;
        // e를 기준으로 오름차순 정렬, 같을 경우 s를 기준으로 정렬
        Arrays.sort(targets, new Comparator<int[]>() {
            public int compare(int[] t1, int[] t2) {
                if (t1[1] == t2[1]) {
                    return t1[0] - t2[0];
                }
                return t1[1] - t2[1];
            }
        });
        // end(요격 미사일의 위치)
        int end = targets[0][1]; // 첫 미사일의 e로 갱신
        // answer 증가
        answer++;
        for (int[] target : targets) {
            // target의 s가 end보다 크거나 같다면
            if (target[0] >= end) {
                // 같이 요격하지 못하므로 미사일을 추가해야 하므로 answer 증가
                answer++;
                // end를 e로 갱신
                end = target[1];
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L105_181188 solution = new L105_181188();

        int[][] targets = { { 4, 5 }, { 4, 8 }, { 10, 14 }, { 11, 13 }, { 5, 12 }, { 3, 7 }, { 1, 4 } };

        int result = solution.solution(targets);

        System.out.println(result);
    }
}