[프로그래머스 요격 시스템] - 파이썬 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/181188?language=python3

프로그래머스

 

문제 요약

각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return한다.

 

풀이

target들끼리 겹치는 구간이 있다면 미사일을 한 번만 쏘면 된다. 반면, target들끼리 겹치는 구간이 없을 경우 별개의 미사일을 또 쏘아야 한다.

따라서 target의 e를 기준으로 오름차순 정렬한 뒤, 다음 target의 s 좌표가 e 좌표보다 같거나 크면 미사일을 따로 쏘아야 한다는 의미이다. 그러므로 필요한 미사일의 개수를 +1 해준다.

 

def solution(targets):
    """
    미사일을 최소로 사용해 요격한다.
    """
    
    # 정렬
    targets.sort(key=lambda x: (x[1], x[0]))
    
    result = 0
    e = 0
    for target in targets:
        if target[0] >= e:
            result += 1
            _, e = target
        
    return result