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

🎨 문제

프로그래머스

📘 풀이

이 문제는 정렬과 그리디로 풀 수 있습니다. 

 

폭격 미사일을 s에 대해 오름차순, e에 대해 내림차순으로 정렬합니다.

// int[][] targets = [[s, e]]
Arrays.sort(targets, (int[] a, int[] b) -> {
    if (a[0] - b[0] == 0) return b[1] - a[1];
    return a[0] - b[0];
});

요격 미사일을 최소한으로 사용해야 하기 때문에 최대한 많은 폭격 미사일이 겹치는 지점을 찾아야 합니다. 폭격 미사일은 (s, e) 구간에서 요격해야 합니다. 앞서 정렬된 폭격 미사일을 순서대로 꺼내오면서 요격 미사일 한 대가 요격할 수 있는 새로운 구간 (s, e)를 구합니다. 만약 다음 폭격 미사일이 요격 미사일 한 대가 요격할 수 없다면 새로운 요격 미사일이 필요하다는 뜻입니다. 새로운 요격 미사일이 요격 가능한 구간을 새로 구해줍니다.

int check(int[][] targets) {
        
    int count = 1;
        
    int s = 0;
    int e = 1000000000;
        
    for (int[] target : targets) {
        int curS = target[0];
        int curE = target[1];
            
        if (curS >= s && curE <= e) {
            s = curS;
            e = curE;
            continue;
        } 
            
        if (curS < e && curE >= e) {
            s = curS;
        }
            
        if (e <= curS) {
            s = curS;
            e = curE;
            count += 1;
        }
    }
        
    return count;
}

📗 코드

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        // 폭격 미사일
        Arrays.sort(targets, (int[] a, int[] b) -> {
            if (a[0] - b[0] == 0) return b[1] - a[1];
            return a[0] - b[0];
        });

        return check(targets);
    }
    
    int check(int[][] targets) {
        
        int count = 1;
        
        int s = 0;
        int e = 1000000000;
        
        for (int[] target : targets) {
            int curS = target[0];
            int curE = target[1];
            
            if (curS >= s && curE <= e) {
                s = curS;
                e = curE;
                continue;
            } 
            
            if (curS < e && curE >= e) {
                s = curS;
            }
            
            if (e <= curS) {
                s = curS;
                e = curE;
                count += 1;
            }
        }
        
        return count;
    }
}

💡 접근법

보통 그리디는 바로 떠오르지 않습니다. 그래서 제가 문제를 풀 때 생각한 방법을 말씀드리겠습니다.

 

폭격 미사일의 최대 개수는 500,000이고 폭격 미사일의 x 좌표 범위는 0부터 100,000,000입니다. 완전탐색으로 푼다면 0부터 100,000,000 중 최소 요격 미사일 개수로 500,000개의 폭격 미사일을 격추시켜야합니다. 완전 탐색으로는 시간이 부족합니다. 요격 미사일의 개수가 최소가 돼야 하기 때문에 이 문제는 최적화 문제라고 할 수 있습니다. 최적화 문제는 결정문제로 바꿀 수 있습니다. 요격 미사일의 개수를 K라 정하면 문제는 다음과 같이 바꿀 수 있습니다.

K개의 요격 미사일로 폭격 미사일을 격추시킬 수 있는가?

요격 미사일의 개수는 0 ~ 100,000,000개 사이입니다. 이 범위를 이분탐색한다면 약 27번만에 K를 결정할 수 있습니다.

방어에 성공하는 요격 미사일의 개수 중 최소를 찾으면 됩니다. 즉, 아래 그림에서 첫 방어 성공이 나오는 K 값이 정답이 됩니다.

요격 미사일 개수에 따른 방어 성공 및 실패

다음은 방어 성공 및 실패 여부를 판단하는 로직을 짜는 것입니다. 여기서 이분 탐색이 아닌 그리디로 문제를 풀 수 있겠다는 아이디어가 떠올랐습니다.

 

다시 말해 O(n^2)인 완전탐색을 고려한 뒤 좀 더 빠른 시간 복잡도를 갖는 방법을 순서대로 고려하여 문제를 풉니다.