문제 소개
문제 링크 (요격 시스템)https://school.programmers.co.kr/learn/courses/30/lessons/181188
문제 설명 및 요구사항
- 2차원 공간이 있을 때, 개구간
(s, e)로 표현되는 각 구간의 어떤 지점x에 미사일을 발사할 때, - 모든 구간을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 구하는 문제
입/출력 예시 분석
| targets | result |
|---|---|
| [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]] | 3 |
(그림 출처: 프로그래머스)
- 최소로 미사일을 쏘기 위해서는 각 구간들이 겹쳐지는 곳에 미사일을 쏘아야 한다.
- 어떤 구간이 미사일에 맞기 위해서는 해당 구간의 시작 지점(
s)가 미사일의 발사 지점(x)보다 왼쪽에 있어야 한다. (= 작아야한다, 개구간 이므로)
문제의 제약 조건
- 1 ≤
targets의 길이 ≤ 500,000 - targets의 각 행은
[s, e]형태이며, 0 ≤s<e≤ 100,000,000
⇒ targets의 길이가 500,000이므로 일반적인 완전 탐색은 사용할 수 없다.
문제 이해
핵심 문제 파악
우선 구간을 한 곳에 모으기 위해 정렬을 한다고 생각해보자. 최대한 각 구간들이 겹쳐지는 곳에 미사일을 쏘려면 어떻게 해야할까? 어떤 미사일 (s ,e)에 대하여 e에 최대한 가깝게 쏘아야 한다. 왜냐하면 요격 지점을 오른쪽으로 최대한 미룰 수록, 그 지점 왼쪾에 시작점을 두고 있는 더 많은 미사일들을 포함할 가능성이 커지기 때문이다.
그렇다면 무엇을 기준으로 정렬해야 할까?
만약에 시작점 기준으로 정렬한다고 가정해보자.
예를 들어 [[1, 100], [2, 3]] 이라는 경우가 있다고 하면 가장 먼저 처리해야 할 미사일은 [1, 100]이 된다. 여기서 100에 가깝게 쏘게 된다면 그 다음에 나오는 [2, 3] 에 대한 정보를 놓치게 된다!
따라서 끝나기 직전에 미사일을 쏜다고 가정했을 때, 내가 가장 급하게 처리해야할 미사일은 가장 먼저 끝나는(e가 가장 작은) 미사일이다.
그리고 어떤 지점에서 미사일을 쏘게 된다면(x라고 가정해보자), 해당 지점을 경계로 어떤 구간의 시작 지점이 x 보다 왼쪽에 있다면 그 미사일이 이 구간에도 영향을 미침을 의미한다. (위의 그림 참고)
따라서 미사일을 끝나는 지점 기준으로 정렬하고, 아직 요격되지 않은 미사일이 나타나면 마지막으로 미사일을 쏜 위치를 갱신하는 방식으로 계산해주면 된다!
시간 복잡도
- 정렬 :
O(nlogn) - 배열 순회 :
O(n)
이므로 총 O(nlogn) 의 시간 복잡도이다.
구현
import java.util.*;import java.io.*;
class Solution {
// 가설: 어떤 구간이 끝나기 전에 미사일을 쏘는게 효율적일 것이다. // 근거: 요격지점을 미룰 수록, 해당 지점 이전에 걸쳐있는 구간의 미사일들이 존재할 가능성이 있음 // -> 그렇다면 가장 급한 미사일은 가장 먼저 끝나는 미사일 => e가 작은 미사일 public int solution(int[][] targets) { // 끝점 기준 오름차순 정렬 Arrays.sort(targets, (a, b) -> Integer.compare(a[1], b[1]));
int latestPoint = targets[0][1]; // 최근 요격 지점 경계값 int count = 1;
for (int i = 1; i < targets.length; i++) { if (targets[i][0] < latestPoint) { // 이전의 요격을 통해 처리된 경우 continue; }
count++; latestPoint = targets[i][1]; }
return count; }}사담
- 처음에 parametric search 를 생각했는데, 그러기 위해서는
check(k)함수, 즉 “k개의 미사일로 모든 구간을 요격할 수 있는가?”를 판별하는 것이 쉽지 않아 보였다. - 이렇게 구간이 있는 문제에서 정렬은 거의 항상 첫 번째로 고려해야 할 도구 인 것 같다. 전체 상황을 한 번에 보려고 하기 보다는, 정렬된 순서대로 하나씩 처리하며 최적의 선택을 쌓아갈 수 있을까?라고 생각해보기…