[Programmers] 요격 시스템 (PYTHON, JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/181188?language=python3

프로그래머스

미사일을 최소로 사용해 모든 폭격 미사일을 요격해야 한다.

그럼 최소에서 힌트를얻어, 가장 많이 겹치는 범위부터 요격하면 되는것 아닌가?싶지만...이 경우 최적해가 아닌 경우가 발생한다.

 

아래경우를 생각해보면 많이겹치는 곳중 빨간부분을 먼저쏘면 4번 요격해야하므로 이 풀이원칙은 반례가 생긴다...

 

 

그럼 포커스를 "최소" 에서 "모든"으로 맞춰보자.

결국 모든 것을 쏴야하는 것이니 작은것부터 순서대로 최대 효율로 처리할 수 있지않을까?

 

가장 일찍 끝나는 미사일에 맞춰 요격 미사일을 발사하면 최대한 많은 폭격 미사일을 커버할 수 있을 것이다.

 

여기서 중요한것은 끝나는 지점에 집중해야한다는 것이다.

 

시작점으로만 정렬하면, 끝나는 지점이 늦은 미사일을 먼저 요격하려다가 뒷부분에 겹치는 미사일들을 놓치는 상황이 발생할 수 있다.

하지만 끝나는 지점이 빠른 미사일부터 처리하면 나중에 더 늦게 끝나는 미사일도 자연스럽게 커버할 가능성이 생긴다.

 

1. 최대한 많은 미사일을 커버할 수 있도록 미사일이 끝나는 지점에 맞춰 요격 미사일을 발사해야 한다.
2. 끝나는 지점 기준으로 미사일을 정렬한 후, 차례대로 각 미사일의 시작점이 현재 커버 범위 밖이면 새로운 요격 미사일을 발사한다.
3. 이 과정을 통해 필요한 최소 요격 미사일의 수를 계산한다.

 

즉, 각 폭격 미사일의 시작점이 현재 요격미사일의 끝지점보다 크면 새로운 요격 미사일이 필요하다.

끝지점으로 정렬후, 현재 미사일로 커버할수없는 범위(위의경우)이면 ans에 +1을 해준다.

 

이해를 돕기위해 아래그림을보자.

각 범위 끝값으로 정렬후, 현재 끝값보다 다음 시작값(빨간색짝,노란색짝끼리 비교)이 크다면 새 요격미사일이 필요하므로 +1해준다.

 

Python

def solution(targets):
    answer = 0
    curr_s = curr_e = 0 # 현재 요격 미사일이 커버할 수 있는 범위
    
    targets.sort(key = lambda x:x[1])
    
    for target in targets:
        if target[0] >= curr_e:
            answer+=1 # 새 요격미사일 필요
            curr_e = target[1] # 끝 지점 업데이트
    
    return answer

 

Java

import java.util.Arrays;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        int curr_e = 0; // 현재 요격 미사일이 커버할 수있는 끝범위
        
        Arrays.sort(targets, (a,b) -> Integer.compare(a[1], b[1]));
        
        for (int[] target : targets) {
            // 현재 요격 미사일이 커버할 수 없는 범위
            if (target[0] >= curr_e) {
                answer++;
                curr_e = target[1]; // 미사일 끝 지점 업데이트
            }
        }
        
        return answer;
    }
}