https://school.programmers.co.kr/learn/courses/30/lessons/181188
문제 파악
targets 배열에 미사일의 구간이 담겨져 있다.
그림에 노란색 부분이 미사일의 구간들이고
우리는 미사일을 저지하는 요격 미사일을 발사해서 저지해야한다.
이때 최소한의 요격미사일로 모든 미사일들을 요격하고 싶다.
최소의 요격미사일의 개수를 return하는 문제이다.
핵심 아이디어
끝점(e) 기준으로 정렬한다.
가능한 한 “가장 오른쪽(끝점)”에서 쏘면, 최대한 많은 구간을 한 번에 커버할 수 있다.
그리고 현재 구간의 시작 s가 이전에 쏜 shot_x 이상이면, 겹치지 않으므로 새로 발사해야 한다.
만약 s < shot_x라면 이미 이전에 쏜 미사일로 커버가 되므로 스킵한다.
해답 및 풀이
def solution(targets):
# 1) 끝점 기준 오름차순 정렬
targets.sort(key=lambda x: x[1])
answer = 0
shot_x = None # 마지막으로 쏜 x(=선택한 끝점)
for s, e in targets:
# 아직 안 쐈거나, 현재 구간이 기존 shot_x와 겹치지 않으면 새로 쏜다.
# [s, e) 라서 s >= shot_x 면 겹치지 않음(= 새 발사 필요)
if shot_x is None or s >= shot_x:
shot_x = e
answer += 1
# s < shot_x 라면 이미 shot_x가 [s,e) 안에 있어서 커버됨 → 패스
return answer
Frontend Engineers