[프로그래머스] Lv2. 요격 시스템

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

프로그래머스

 

문제 설명

최소 미사일 발사 몇번을 통해서 방어할 수 있는가에 대한 문제였다.

 

풀이

이 문제의 경우 또 그래프인가? 탐색문젠가 브루트포스인가 병적으로 ㅎㅎ;; 생각하다가... 알고보니 정렬하면 쉽게 끝나는 문제였다. (s,e)범위라 할 때, e를 기준으로 정렬한 후에, 앞선 범위의 마지막 부분이 이번 부분의 앞부분보다 앞에 있을 경우 새로운 미사일이 필요함을 인지하면 된다. 

 

 

최종코드

def solution(targets):
    answer = 0
    
    targets.sort(key=lambda x:[x[1], x[0]])
    
    s = e = 0
    
    for target in targets:
        if target[0] >= e:
            answer+=1
            e = target[1]
        
    return answer