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

프로그래머스 요격 시스템

비슷한 문제 (백준 1931 회의실 배정)

그리디 알고리즘을 활용한 문제였다. 비슷한 문제인 회의실 배정에서는 회의가 시작하는 시간이 빨라도 늦게 끝나면 최대 회의의 수를 맞출 수 없기 때문에 회의의 종료시간이 중요했다. 이 문제에서는 모든 미사일을 제거해야 했기 때문에, 왼쪽(x = 0)부터 탐색한다는 가정 하에 미사일의 오른쪽을 기준으로 정렬해야 해당 미사일을 제거하기 위해서 최소한 어느 부분을 쏴야 하는지 알 수 있다. 또한 마지막에 쐈던 미사일의 위치를 기억함으로써 이미 제거된 미사일은 고려하지 않도록 할 수 있다.

1. 미사일의 오른쪽을 기준으로 오름차순으로 정렬한다.
2. 마지막에 쏜 요격 미사일의 좌표값을 기억한다.
3. 정렬한 미사일을 탐색하며, 만약 이미 요격된 미사일이라면 무시한다.
4. 아직 요격하지 않은 미사일이라면, 미사일을 요격할 수 있는 좌표중 최댓값으로 요격 미사일을 발사하고, 마지막에 쓴 요격 미사일의 좌표를 업데이트 한다.

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int last = 0;
        int cnt = 0;
        ArrayList <int []> missiles = new ArrayList <>(Arrays.asList(targets));
        missiles.sort((a, b) -> a[1] - b[1]);
        for (int [] missile : missiles){
            if (missile[0] >= last){
                last = missile[1];
                cnt++;
            }
        }
        return cnt;
    }
}