문제 요약
각 폭격 미사일은 개구간 (s, e)로 주어진다.
요격 미사일은 하나의 x 좌표에서 발사하며, 해당 좌표가 폭격 미사일의 구간 내부에 있으면 요격할 수 있다.
단, 구간은 개구간이므로 s와 e에서는 요격할 수 없다.
모든 폭격 미사일을 요격하기 위한 요격 미사일 수의 최솟값을 구해야 한다.
핵심 아이디어
가장 빨리 끝나는 폭격 미사일부터 처리한다.
현재 폭격 미사일의 종료 좌표가 e라면, 이 구간을 요격하기 위한 미사일은 e보다 아주 조금 작은 위치에 발사하는 것이 가장 유리하다.
요격 위치 = e - ε이 위치는 현재 구간을 요격하면서, 이후에 시작하는 다른 구간도 가능한 많이 함께 요격할 수 있다.
실수 ε를 직접 사용할 필요는 없다. 마지막으로 선택한 종료 좌표를 last_end에 저장하고, 다음 구간의 시작 좌표 s와 비교하면 된다.
s < last_end: 이전 미사일 위치last_end - ε가 현재 구간 내부에 있다.s >= last_end: 이전 미사일 위치가 현재 구간 내부에 없으므로 새 미사일이 필요하다.
개구간에서 비교 연산자가 중요한 이유
닫힌 구간이라면 시작점이 이전 종료점과 같을 때 같은 요격 위치를 사용할 수 있다.
하지만 이 문제의 구간은 (s, e)다. 이전 미사일은 last_end보다 작은 위치에 발사되므로, 다음 구간의 시작점이 last_end와 같으면 다음 구간의 내부에 포함되지 않는다.
따라서 새 미사일이 필요한 조건은 다음과 같다.
if start >= last_end:>가 아니라 >=를 사용해야 한다.
풀이 과정
- 모든 폭격 미사일 구간을 종료 좌표 기준 오름차순으로 정렬한다.
- 아직 요격 미사일을 발사하지 않았다는 의미로
last_end를 작은 값으로 초기화한다. - 정렬된 구간을 순회한다.
- 현재 구간의 시작점이
last_end이상이면 새 요격 미사일을 발사한다. - 새 미사일을 발사한 경우 현재 구간의 종료점으로
last_end를 갱신한다. - 필요한 미사일 수를 반환한다.
Python 코드
def solution(targets):
targets.sort(key=lambda target: target[1])
answer = 0
last_end = -1
for start, end in targets:
# 이전 요격 위치는 last_end - ε 이다.
if start >= last_end:
answer += 1
last_end = end
return answer코드 설명
종료 좌표 기준 정렬
targets.sort(key=lambda target: target[1])종료점이 가장 이른 구간부터 처리한다.
현재 구간의 종료점 바로 앞에 요격 미사일을 두면, 현재 구간을 요격하면서 이후 구간과 겹칠 가능성을 가장 크게 유지할 수 있다.
새 요격 미사일 발사 조건
if start >= last_end:last_end는 실제 요격 위치가 아니라, 실제 요격 위치가 last_end - ε임을 나타내는 기준값이다.
현재 구간의 시작점이 last_end보다 작을 때만 이전 요격 위치가 현재 개구간 내부에 포함된다.
시작점이 같거나 더 크면 이전 미사일로는 요격할 수 없으므로 새 미사일이 필요하다.
정확성
종료 좌표가 가장 이른 구간을 생각하자. 이 구간을 요격하려면 반드시 종료점보다 작은 어떤 위치에 요격 미사일을 발사해야 한다.
그중 종료점 바로 앞 위치를 선택하면 현재 구간을 요격하면서, 다른 가능한 위치보다 오른쪽에 있으므로 이후 구간을 함께 요격할 가능성을 줄이지 않는다.
따라서 가장 이른 종료점 바로 앞에 미사일을 발사하는 선택은 항상 최적해에 포함될 수 있다.
이후 이전 미사일 위치가 내부에 포함되는 모든 구간은 추가 미사일 없이 요격한다. 포함되지 않는 첫 구간에서는 반드시 새 미사일이 필요하므로, 같은 방식으로 종료점 바로 앞에 미사일을 발사한다.
이 과정을 반복하면 각 단계에서 필요한 미사일을 최소 하나씩만 추가하므로 전체 요격 미사일 수도 최소가 된다.
시간 복잡도
폭격 미사일 수를 N이라고 하자.
구간 정렬에 O(N log N), 정렬된 구간 순회에 O(N)이 걸린다.
O(N log N)공간 복잡도
정렬은 입력 배열 내부에서 수행하며, 추가로 사용하는 변수는 상수 개다.
O(1)정렬 구현에 따라 내부 정렬 공간이 추가로 사용될 수 있다.
주의할 점
- 이 문제의 폭격 미사일 범위는 닫힌 구간이 아닌 개구간이다.
- 구간 끝점에서 요격할 수 없으므로
end가 아닌end - ε위치를 선택하는 것으로 생각해야 한다. - 따라서 새 미사일 조건은
start > last_end가 아니라start >= last_end다. - 실수 값을 직접 저장할 필요 없이 종료 좌표 정수만 저장하면 된다.
- 시작점 기준이 아니라 종료점 기준으로 정렬해야 그리디 선택이 성립한다.
정리
이 문제는 종료점이 가장 이른 구간부터 처리하는 구간 선택 그리디 문제다.
각 요격 미사일을 현재 구간의 종료점 바로 앞에 둔다고 생각하고, 다음 구간의 시작점이 이전 종료점 이상일 때만 새 미사일을 추가하면 최소 횟수를 구할 수 있다.
