[programmers/py] 요격 시스템

요격 시스템

https://school.programmers.co.kr/learn/courses/30/lessons/181188

문제 요약

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

풀이

• 그리디 알고리즘

위 사진을 보면 각 요격 지점이 11, 4, 1이다.
11에 의해 요격 당하는 미사일을 보면 e값이 11보다 큰 경우다.
즉, e<=11이면 새로운 요격 구간이 추가되고 그 s값을 요격 범위로 잡느다.

def solution(targets):
    answer = 1
    targets.sort(key = lambda x:-x[0],)

    hit = targets[0][0]
    for s, e in targets:
        if e <= hit:
            answer += 1
            hit = s
    return answer