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

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

프로그래머스

문제 설명

A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다.
A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.
A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다.
각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• 1 ≤ targets의 길이 ≤ 500,000
• targets의 각 행은 [s,e] 형태입니다.
• 이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
• 0 ≤ s < e ≤ 100,000,000

해결 아이디어

우리가 구해야 하는 답은 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값입니다.

즉, 우리가 발사하는 각각의 요격 미사일은 최대한 많은 폭격 미사일을 요격할 수 있어야 합니다.

 

만약 폭격 미사일 중 하나가 개구간 (3, 7)로 주어진다면, 우리는 어쨋건 4, 5, 6 구간중 한 구간 이상에서 요격 미사일을 발사하여야 합니다. 그런데 이 때, 개구간 (4, 9) 구간에 폭격 미사일이 하나가 더 주어 진다면, 우리는 5, 6 구간 중 한 구간에서 요격 미사일을 발사하여 하나의 요격 미사일로 두개의 폭격 미사일을 요격할 수 있게 됩니다.

반대로, (7, 10) 구간에 폭격 미사일이 주어진다면 우리는 최소한 두개 이상의 미사일을 사용하여야 합니다.

 

주어진 (3, 7) 미사일에 대해 (4, 9) 구간의 폭격 미사일과 (7, 10) 구간의 폭격 미사일이 가지는 차이에 대해 고민해 보면 좋을 것 같습니다. 

 

우리는 이제 앞에서부터 차근차근 미사일을 요격하기 위해 필요한 요격 미사일의 개수를 탐색할 것입니다.

탐색하는 방법은 다음과 같습니다.

1. 폭격 미사일을 끝나는 구간 e를 기준으로 오름차순으로 정렬합니다.
2. 새로운 요격 미사일이 필요하게 되는 첫 폭격 미사일의 위치를 기억하며 미사일의 개수를 1 증가 시킵니다.
3. 첫 폭격 미사일의 다음부터 첫 폭격 미사일의 종료 위치보다 앞 구간에서 시작하는 모든 폭격 미사일을 탐색합니다.
4. 탐색하는 미사일이 첫 폭격 미사일의 종료 위치보다 크거나 같은 구간에서 시작하는 경우 해당 미사일을 2.의 첫 미사일로 기억하고 2부터 다시 탐색을 수행합니다.

해당 알고리즘이 동작할 수 있게 되는 조건은 문제에서 주어진 미사일은 실수인 x 좌표에서도 발사할 수 있다는 조건 때문입니다. 즉, (3, 7) 미사일에 대해서 6.99999... 구간에서 요격 미사일을 발사하여 최대한 많은 이후의 미사일을 해결할 수 있도록 하는 것입니다. 이렇게 하면 7 이전 구간에서 시작하는 모든 미사일이 해당 미사일과 같은 요격 미사일로 격추될 수 있습니다.

 

2~4의 탐색 알고리즘은 전체 배열에서 반복적으로 구간의 시작과 끝 구간을 갱신하며 탐색하는 "투 포인터" 기법으로 구현할 수 있습니다.

소스 코드

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        
        int missile = 1;                
        Attack[] atacks = new Attack[targets.length];
        for(int i = 0; i<targets.length; i++)
            atacks[i] = new Attack(targets[i][0], targets[i][1]);
        Arrays.sort(atacks);
        
        int start = 0;
        int end = 0;
        while(end < targets.length){
            if(atacks[end].start < atacks[start].end)
                end++;
            else{
                missile++;
                start = end;
            }
        }
        
        return missile;
    }
}
class Attack implements Comparable<Attack>{
    int start;
    int end;
    
    public Attack(int s, int e){
        this.start = s;
        this.end = e;
    }
    
    public int compareTo(Attack a){
        if(this.end == a.end)
            return this.start - a.start;
        return this.end - a.end;
    }
}