프로그래머스 요격 시스템 자바 풀이

문제 링크

문제 요약

폭격 미사일의 x 좌표 범위가 개구간 (s, e)로 주어진다
요격 미사일 하나는 특정 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통해서 요격한다
모든 폭격 미사일을 요격하는 데 필요한 최소 요격 미사일 수를 구한다

문제 풀이

처음에는 모든 폭격 미사일 쌍을 비교해서 겹치는 것끼리 묶으면 되겠다고 생각했다.

하지만 이 방식은 비효율적이다.

targets의 길이가 최대 500,000인데, 모든 쌍을 비교하면 경우의 수가 n^2이라 2500억에 가까워진다.

이 문제의 핵심은 구간을 정렬한 뒤, 겹치는 구간들을 하나의 요격 미사일로 최대한 묶어나간다는 점이다.

구간을 시작 좌표 기준으로 정렬하고, 현재까지 묶인 구간들이 겹치는 끝 좌표를 하나 들고 있는다.

다음 구간의 시작이 그 끝 좌표보다 작으면 아직 겹칠 수 있으므로, 끝 좌표를 두 구간 중 더 작은 값으로 좁혀서 계속 묶는다.

다음 구간의 시작이 끝 좌표보다 같거나 크면 더 이상 겹치지 않으므로, 지금까지 묶인 구간을 요격 미사일 하나로 확정하고 새 구간부터 다시 묶기 시작한다.

개구간이라서 경계값이 정확히 같은 경우는 겹치는 것으로 치지 않아도 되고, 요격 미사일은 실수 좌표에서도 쏠 수 있으므로 겹치는 구간 안 어딘가에만 있으면 된다.

정렬에 O(n log n)이 걸리고 이후에는 한 번씩만 훑으므로 전체 시간 복잡도는 O(n log n)이다.

최종 코드

java

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 1; // 첫 구간을 요격하는 미사일 1개는 항상 필요
        
        // 시작 좌표 기준 정렬, 같으면 끝 좌표 기준
        Arrays.sort(targets, (o1, o2)->{
           if(o1[0] == o2[0])
               return Integer.compare(o1[1], o2[1]);
            return Integer.compare(o1[0], o2[0]);
        });
        
        int end = targets[0][1]; // 현재 묶여 있는 구간들이 겹치는 끝 좌표
        
        for(int i=1;i<targets.length;i++){
            if(targets[i][0] < end){ // 아직 겹치는 구간이면 끝 좌표를 좁혀서 계속 묶는다
                end = Math.min(end, targets[i][1]);
                continue;
            }
            
            end = targets[i][1]; // 더 이상 안 겹치므로 새 요격 미사일로 다시 시작
            answer++;
        }
        
        return answer;
    }
}

요격 시스템

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기