[Level 2 | Python] 요격 시스템

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

프로그래머스

문제

A 나라가 B 나라에 미사일을 보낸다. 이 세계관은 2차원 공간이다. X축과 평행한 방향으로 미사일이 떨어진다. 요격 미사일은 Y축과 평행하게 날라가고 그 위치에 있는 적 미사일들을 다 요격할 수 있다. 요격해서 미사일을 안 맞을 수 있는 최소한의 요격 미사일 갯수 구하기 문제이다. 

풀이 과정

그리디 문제이다.

x좌표를 나타내는 정수 쌍 (s,e) 형태로 주어지는데 어차피 s가 e보다 크면 같이 요격할 수 없고 요격 미사일을 하나 더 써야 한다. 

그래서 e를 기준으로 정렬하고 for 문을 돌면서 s가 e보다 answer+=1을 해주면 끗!

시간복잡도
정렬인 O(NlogN) + 탐색 O(N) = O(NlogN)

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