프로그래머스 | Level 2 | 요격 시스템

Oct 24, 2024

Published byJin

999

Programmers | Level 2 | 요격 시스템

Problems

📘 Src: Programmers
🗂️ Cat: Greedy

󰧭 Description

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 함수를 완성해 주세요.

 Constraints

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

󰦕 Examples

targets	result
`[[4,5],[4,8],[10,14],[11,13]]`	2

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        // 미사일의 끝점 기준으로 정렬하여 가장 적은 미사일을 사용할 수 있게 설정
        Arrays.sort(targets, (a, b) -> a[1] - b[1]);  
        
        int intercept = 0;  // 요격 미사일 수
        int lastEnd = 0;  // 마지막 요격 미사일의 요격 범위 끝점
        
        for (int[] target : targets) {
            // 현재 미사일이 이전 요격 범위 밖에 있으면 새로운 요격 미사일 발사
            if (target[0] >= lastEnd) {
                intercept++;  // 요격 미사일 수 증가
                lastEnd = target[1];  // 새로운 요격 미사일의 범위를 끝점으로 설정
            }
        }
        
        return intercept;  // 최소 요격 미사일 수 반환
    }
}

 Approaches

이 문제는 주어진 미사일의 경로를 최소한의 미사일로 요격하는 탐욕법(Greedy) 알고리즘 문제입니다. 미사일 경로를 정렬한 후, 각 미사일의 끝점을 기준으로 요격 미사일을 발사하여 최소 요격 미사일 수를 계산합니다.

1. 문제 분석

각 미사일은 [시작점, 끝점]으로 표현된 경로를 가지고 있으며, 여러 미사일이 겹치는 경우 하나의 요격 미사일로 동시에 처리할 수 있습니다. 하지만, 겹치지 않는 미사일이 있으면 추가 요격 미사일이 필요합니다. 목표는 모든 미사일을 최소한의 요격 미사일로 처리하는 것입니다.

이를 위해 미사일 경로를 끝점을 기준으로 정렬합니다. 끝점을 기준으로 정렬하는 이유는, 현재 요격 미사일이 미사일의 끝나는 지점에 맞춰 발사되었을 때 겹치는 미사일들을 최대한 많이 처리할 수 있기 때문입니다. 만약 다음 미사일의 시작점이 현재 요격 미사일의 끝점보다 크다면, 그 미사일은 이전 미사일과 겹치지 않기 때문에 새로운 요격 미사일이 필요합니다. 끝점을 기준으로 정렬하면, 미사일이 겹치는 구간을 쉽게 확인할 수 있어 최소한의 요격 미사일로 모든 미사일을 처리할 수 있습니다.

2. 접근 방식

이 문제는 그리디 알고리즘을 사용하여 해결할 수 있습니다. 미사일 경로를 끝점 기준으로 정렬한 뒤, 요격 미사일을 최대한 효율적으로 사용합니다.

정렬: 먼저 미사일 경로의 끝점을 기준으로 오름차순으로 정렬합니다. 이는 요격 범위를 최소화하고, 가능한 많은 미사일을 한 번에 처리하기 위함입니다.
그리디 탐색: 정렬된 미사일 경로를 순차적으로 확인하면서, 요격 범위에 포함되지 않는 미사일이 나타날 때마다 새로운 요격 미사일을 발사합니다. 이전 미사일의 끝점이 다음 미사일의 시작점 보다 크거나 같으면 같은 요격 미사일로 처리할 수 있지만, 그렇지 않다면 새로운 요격 미사일이 필요합니다.

3. 요격 범위 설정 및 초기화

미사일의 끝점 기준으로 정렬한 후, 요격 범위와 요격 미사일 수를 추적합니다. 첫 번째 미사일을 처리하기 위해 새로운 요격 미사일을 발사하고, 이후에는 겹치는 미사일을 처리하면서 필요한 최소 미사일 수를 구합니다.

Solution.java

Arrays.sort(targets, (a, b) -> a[1] - b[1]);  // 끝점 기준으로 정렬
int intercept = 0;  // 요격 미사일 수를 기록
int lastEnd = 0;  // 마지막 요격 범위의 끝점

4. 요격 미사일 발사 및 탐색

정렬된 미사일 경로를 순차적으로 탐색하면서, 현재 미사일이 이전 요격 범위에 속하지 않으면 새로운 요격 미사일을 발사합니다. 새로운 요격 미사일의 요격 범위는 해당 미사일의 끝점으로 설정됩니다.

Solution.java

for (int[] target : targets) {
    if (target[0] >= lastEnd) {  // 현재 미사일이 이전 요격 범위를 벗어났을 때
        intercept++;  // 새로운 요격 미사일 발사
        lastEnd = target[1];  // 요격 범위를 갱신
    }
}

5. 최종 결과 반환

모든 미사일을 탐색한 후, 필요한 최소 요격 미사일의 수를 반환합니다.

Solution.java

// 최종 요격 미사일 수 반환
return intercept;

󰄉 Complexity

⏳ TC: O(n log n)
💾 SC: O(1)

시간 복잡도는 주어진 미사일 경로를 정렬하는 데 O(n log n)이 소요되며, 그 후에는 한 번의 탐색을 통해 요격 미사일을 계산하므로 O(n)의 시간이 추가로 소요됩니다. 따라서 총 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 상수 공간을 사용하므로 O(1)입니다.

Algorithm
Greedy