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

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• ✅ 알고리즘 설계
• 🧠 그리디 알고리즘 적용 방식
• 🔍 최종 코드
• 💻 실행 흐름 예시
• 💡 핵심 포인트
• 🕑 시간 복잡도

 

 

 

 

🔗 문제 바로가기

프로그래머스

 

 

📌 문제 요약

1️⃣ 2차원 평면에서 여러 개의 폭격 미사일이 (s, e)의 x축 개구간으로 날아온다.

2️⃣ B국은 특정 x 좌표에서 요격 미사일을 쏴서 해당 x좌표를 포함하는 모든 미사일을 한 번에 요격할 수 있다.

3️⃣ 단, s와 e 위치에서 쏘는 것은 요격으로 인정되지 않으며, (s < x < e) 안의 실수 좌표여야 한다.

4️⃣ 모든 폭격 미사일을 최소한의 요격 미사일로 방어해야 된다.

 

 

✅ 알고리즘 설계

처음 이 문제를 보고, 제일 중요한 건 미사일의 개수를 줄이기 위한 최적의 타이밍이라고 생각했다.

폭격 미사일 구간 (s, e)를 보면, 이는 어떤 연속된 범위를 의미하고,

우리는 그 구간을 한 점으로 커버할 수 있다는 점에서 활동 선택 문제 (Interval Scheduling Problem)와 유사하다고 생각했다.

따라서, 이 문제는 전형적은 그리디 알고리즘으로 접근할 수 있을 것이다.

 

 

🧠 그리디 알고리즘 적용 방식

핵심 아이디어는 아래의 두 개이다.

1️⃣ 가능한 한 많은 미사일을 한 번에 요격하기 위해서는 끝나는 지점이 가장 빠른 미사일을 기준으로 쏘는 것이 유리하다.

2️⃣ 정렬 기준을 끝점 기준 오름차순으로 하면, 가장 먼저 끝나는 구간부터 탐색할 수 있을 것이다.

Arrays.sort(targets, (o1, o2) -> o1[1] - o2[1]);

 

 

🔍 최종 코드

class Solution {
    public int solution(int[][] targets) {
        Arrays.sort(targets, (o1, o2) -> o1[1] - o2[1]); // 끝점을 기준으로 정렬
        int currEnd = -1; // 현재 요격 미사일이 커버하는 끝점
        int answer = 0; // 요격 미사일의 수

        for(int[] t: targets){
            if(currEnd == -1){ // 첫 미사일인 경우
                answer++;
                currEnd = t[1];
                continue;
            }

            if(t[0] < currEnd){
                // 현재 요격으로 커버 가능하므로 건너뜀
                continue;
            }

            // 커버할 수 없는 경우 새로운 요격 미사일 발사
            answer++;
            currEnd = t[1];
        }

        return answer;
    }
}

 

 

👩🏻‍💻 실행 흐름 예시

[[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]

프로그래머스에 있는 예시를 이용해서 분석해보면 아래와 같은 흐름으로 동작한다.

 

1️⃣ 끝점을 기준으로 오름차순으로 정렬한다. 👉🏻 [[1,4],[4,5],[3,7],[4,8],[5,12],[11,13],[10,14]]

2️⃣ 첫 미사일 (1, 4)를 요격한다. 👉🏻 currEnd = 4, answer = 1 

3️⃣ 다음 미사일 (4, 5)를 보면, 4 < 4 이므로 false여서 요격이 필요함 👉🏻 currEnd = 5, answer = 2

4️⃣ 다음 미사일 (3, 7)은 3 < 5이므로 true여서 이미 커버됨 👉🏻 continue

5️⃣ 다음 미사일 (4, 8)도 4 < 5이므로 true여서 이미 커버됨 👉🏻 continue

6️⃣ 다음 미사일 (5, 12)는 5 < 5이므로 false여서 요격이 필요함 👉🏻 currEnd = 12, answer = 3

7️⃣ 나머지 미사일들은 전부 s < 12 이므로 true여서 이미 다 커버됨 👉🏻 continue

✅ 따라서 최종 요격 미사일 수는 answer = 3임

입출력 예 이미지

 

 

💡 핵심 포인트

1️⃣ 끝점을 기준으로 오름차순 정렬하는 것이 핵심

2️⃣ 개구간 (s, e)이기 때문에 x = e는 포함되지 않음을 주의하기

 

 

🕑 시간 복잡도

정렬: O(N log N)

순회: O(N)

👉🏻 전체 시간 복잡도: O(N log N)