[프로그래머스 Lv.2] 요격 시스템(Java) - 그리디

📌 핵심 요약

• 문제 재진술 — 미사일과 요격이라는 표현을 지우면 "구간들을 모두 찌르는 최소 개수의 점"을 구하는 문제다.
• 정렬 기준 — 끝값(e) 오름차순으로 정렬하면 최소 끝값 탐색이 해결된다.
• 경계 조건 — 개구간이므로 s == shot도 커버되지 않은 것으로 취급해야 한다. 비교 연산자는 >=다.
• 상태 설계 — 필요한 정보는 스칼라 두 개뿐이므로 덱이나 리스트가 필요하지 않다.
• 정렬 습관 — 뺄셈 비교 대신 Integer.compare를 쓰면 입력 범위와 무관하게 안전하다.

 

목차

Programmers #181188

요격 시스템

표적 개수 ≤ 500,000 · 좌표 ≤ 100,000,000

난이도: Lv.2

표적은 개구간 (s, e)로 주어진다. 미사일은 한 점 x에서 발사되며 s < x < e를 만족하는 표적을 요격한다. 모든 표적을 요격하기 위해 필요한 미사일의 최소 개수를 구한다.

풀이 과정

1. 표적을 끝값 e 기준 오름차순으로 정렬한다.
2. 마지막으로 발사한 위치를 shot 변수 하나로 유지한다.
3. 현재 표적이 shot으로 커버되지 않으면 발사 횟수를 늘리고 shot을 갱신한다.

1 규모 판단과 유형 후보 소거

코드를 작성하기 전에 제약 조건을 먼저 확인했다.

항목	값	함의
표적 개수 n	최대 500,000	O(n²) 불가, 목표는 O(n log n)
좌표 범위	최대 100,000,000	좌표축 전체를 순회하는 접근은 배제

두 번째 줄이 중요했다. 좌표 범위가 작았다면 "좌표별로 몇 개 구간이 덮고 있는지"를 세는 누적 합 계열을 떠올릴 수 있었다. 하지만 범위가 1억이므로 좌표를 직접 다루지 않고 구간 자체를 다뤄야 한다고 판단했다. 그리고 목표 복잡도가 O(n log n)이라면 정렬 한 번은 이미 예산 안에 들어 있다는 뜻이었다.

후보를 늘어놓고 지우기

후보	판단	근거
완전탐색	배제	점의 후보 위치가 사실상 무한하다
DP	보류	정의는 가능하나 개수만 묻는 문제에 과하다
그리디	채택	1차원 순서 구조 + 최솟값 요구
누적 합 / 스위핑	배제	좌표 범위가 크고, 덮인 횟수가 아니라 점 개수를 묻는다

DP를 완전히 지우지 않고 보류로 남겨 둔 이유는, 그리디 가설이 반례로 무너질 경우 후퇴할 곳이 필요했기 때문이다. 다만 먼저 그리디를 시도했다.

2 그리디 기준 세우기

그리디에서 정할 것은 하나뿐이다. 어떤 기준으로 선택하면 손해가 없는가.

발상은 이러했다. 점을 하나 찍을 때 가능한 한 오른쪽에 찍으면 뒤에 오는 구간까지 덮을 기회가 커진다.

그렇다면 오른쪽으로 밀 수 있는 한계선은 어디인가.

지금 반드시 처리해야 하는 구간들 중 가장 빨리 끝나는 것의 끝값이다. 그 선을 넘으면 해당 구간을 놓치게 된다.

ℹ️

그리디 가설

끝값이 가장 작은 구간의 끝 바로 왼쪽에 점을 찍는다. 그 점으로 덮이는 구간을 모두 지운다. 남은 것에 대해 반복한다.

증명보다 먼저 반례

가설을 믿기 전에 작은 케이스로 흔들어 보았다. 구조가 특이한 세 가지를 골랐다.

케이스	입력	가설의 답	정답	통과
포함 관계	[1,10] [2,3]	[2,3] 먼저 처리 → 1개	1	일치
완전 분리	[1,2] [5,6]	2개	2	일치
끝점 = 시작점	[1,4] [4,5]	4의 왼쪽 → [4,5] 미커버 → 2개	2	일치

 개구간이라는 조건이 여기서만 드러났고, 나중에 비교 연산자를 >로 쓸지 >=로 쓸지가 이 한 줄에서 결정되었다.

반례 사냥이 곧 경계 조건 발견이었다.

3 상태 설계 — 덱이 필요 없었던 이유

처음에는 ArrayDeque에 int[]{s, e}를 담아 두고 그룹 단위로 처리하려 했다. 하지만 무엇을 나중에 다시 꺼내 볼 것인지 자문하니 답이 나왔다. 꺼내 볼 것이 없었다.

값	어디에 두는가	근거
구간 하나의 s, e	루프 변수	판정 직후 버려도 무방하다
마지막 발사 위치	바깥 변수	순회 전체에 걸쳐 유지되어야 한다
발사 횟수	바깥 변수	같은 이유

BFS에서 "노드별 상태는 큐에, 컴포넌트 전체 속성은 바깥 변수에"를 구분했던 것과 같은 원칙이다. 다만 이 문제에서 그룹 전체 속성은 스칼라 두 개로 끝나므로 자료구조가 아예 필요하지 않았다.

💡

자료구조 필요 여부 판정

"여기에 담은 값을 나중에 다시 꺼내 볼 일이 있는가?" 이 질문에 아니라고 답할 수 있으면 변수 하나로 충분하다.

s 정렬과 e 정렬의 차이

처음 떠올린 것은 s 기준 정렬이었다. 그쪽도 정답에 이르지만 관리할 상태가 하나 더 늘어난다.

구분	s 정렬	e 정렬
바깥 변수	minEnd, answer	shot, answer
루프 내 분기	2갈래 (새 그룹 / 갱신)	1갈래 (미커버면 발사)
최소 끝값 갱신	Math.min 필요	정렬이 보장하므로 불필요
루프 종료 후 처리	마지막 그룹 +1 필요	없음

e 정렬에서 갱신이 사라지는 이유가 핵심이다. e 오름차순이면 그룹에 새로 들어오는 구간의 끝값은 항상 현재 기준점보다 크거나 같다. 즉 최소 끝값은 그룹의 첫 구간이 확정하고 이후 바뀌지 않는다. s 정렬에서 손으로 갱신했던 일을 정렬이 대신 해 주는 셈이다.

4 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        // 끝값이 작은 구간부터 처리하면, 그 구간의 끝 직전이 최적 발사 위치가 된다
        Arrays.sort(targets, (a, b) -> Integer.compare(a[1], b[1]));

        int answer = 0;
        int shot = -1;   // 마지막 발사 위치. -1은 아직 발사하지 않았음을 의미

        for (int[] target : targets) {
            int s = target[0];
            int e = target[1];

            // shot은 실제로 'e 바로 왼쪽'을 뜻하므로 s == shot도 미커버로 취급
            if (s >= shot) {
                answer++;
                shot = e;
            }
        }
        return answer;
    }
}

시간 복잡도는 정렬이 O(n log n)이고, 추가 공간은 상수다.

좌표를 더하거나 곱하지 않고 비교와 대입만 하므로 int로 충분하다.

추적

입력 [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]을 e 오름차순으로 정렬하면 [1,4] [4,5] [3,7] [4,8] [5,12] [11,13] [10,14] 순서가 된다.

구간	s	shot(직전)	s >= shot	동작	shot(이후)	answer
[1,4]	1	-1	참	발사	4	1
[4,5]	4	4	참	발사	5	2
[3,7]	3	5	거짓	커버됨	5	2
[4,8]	4	5	거짓	커버됨	5	2
[5,12]	5	5	참	발사	12	3
[11,13]	11	12	거짓	커버됨	12	3
[10,14]	10	12	거짓	커버됨	12	3

두 번째와 다섯 번째 행이 개구간 조건이 작동하는 지점이다.

s == shot인 상황에서 발사를 선택했고, 이 부분을 >로 썼다면 두 케이스 모두 틀렸을 것이다.

5 실수했던 부분

뺄셈 비교로 정렬 기준을 작성했다

처음 제출한 코드는 (a, b) -> a[1] - b[1]이었다.

comparator가 참조하는 것은 반환값의 부호뿐이므로 뺄셈으로도 동작한다고 판단했다.

이 문제에서는 실제로 통과했다. e가 항상 0 이상이고 최대 1억이므로 차이가 int 상한을 넘지 않는다.

문제는 안전성의 근거가 코드 안에 없고 문제 지문에 있다는 점이었다.

부호가 섞인 값을 다루는 문제에 같은 습관을 가져가면 조용히 틀린다. a[1] = 2000000000, b[1] = -2000000000인 경우를 따라가 보면 이렇게 된다.

단계	값
수학적 결과	4,000,000,000
int 표현 범위	최대 2,147,483,647 → 초과
실제 저장값	-294,967,296
comparator 판정	음수 → "a가 앞"
참값	a가 더 크므로 뒤에 와야 함

🚨

TimSort 계약 위반

오버플로로 부호가 뒤집히면 "a가 b보다 앞이면서 동시에 뒤"인 모순이 생겨 IllegalArgumentException: Comparison method violates its general contract!가 던져질 수 있다. 병합 과정에서 모순을 실제로 마주쳐야 발생하므로, 작은 테스트는 통과하고 큰 입력에서만 실패하는 형태로 나타난다.

해결. Integer.compare로 교체했다. JDK 구현은 산술 연산 없이 비교 연산만 하므로 오버플로가 발생할 계산 자체가 없다.

 

Java — Integer.compare 구현과 사용

// JDK 구현 — 뺄셈이 없다
public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

// 안전성이 문제 제약에 의존 — 이 문제에서는 동작하지만 습관으로는 부적절
Arrays.sort(targets, (a, b) -> a[1] - b[1]);

// 입력 범위와 무관하게 항상 옳음
Arrays.sort(targets, (a, b) -> Integer.compare(a[1], b[1]));

// 기준이 여러 개일 때
Arrays.sort(targets, Comparator
        .<int[]>comparingInt(t -> t[1])
        .thenComparingInt(t -> t[0]));

⚠️

타입별 위험도

long을 (int)(a - b)로 캐스팅하면 오버플로에 더해 상위 비트가 소실된다. double은 더 치명적이다. 1.5와 1.0의 차이 0.5가 int 캐스팅에서 0이 되어 "두 값이 같다"로 판정된다. 각각 Long.compare, Double.compare를 쓴다.

ℹ️

박싱 오해

Integer라는 클래스 이름 때문에 박싱을 걱정했으나, compare의 파라미터 타입은 int, int 원시형이다. 박싱이 일어나지 않고 JIT가 인라이닝하므로 뺄셈과 실질적인 성능 차이가 없다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.