프로그래머스_요격 시스템

문제

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

프로그래머스

풀이

1. (s, e)를 끝점(e) 기준으로 정렬한다. 
2. 위치 0.5(shoot = 0.5)인 곳에서 미사일을 발사한다.
3. 직전 미사일 발사위치(shoot)와 군사기지(target)의 시작점을 비교한다.
   • 직전 미사일 발사위치(shoot) < 군사기지(target)의 시작점 
     • 군사기지의 종료점-0.5에서 미사일을 발사한다.
     • 미사일 발사 지점을 저장한다. (shoot = target[1]-0.5)
4. 다음 군사기지로 이동하여 탐색(3~4)한다.

EXAMPLE

기지 정보 정렬

[[1, 4], [4, 5], [3, 7], [4, 8], [5, 12], [11, 13], [10, 14]]

미사일 발사(shoot=0.5)

직전 미사일 발사위치(shoot=0.5)와 군사기지(1~4)의 시작점을 비교

=> 직전 미사일로 처리되지 않은 기지이므로, 새로운 미사일을 발사해야 한다.

직전 미사일 발사위치(shoot=3.5)와 군사기지(4~5)의 시작점을 비교

=> 직전 미사일로 처리되지 않은 기지이므로, 새로운 미사일을 발사해야 한다.

직전 미사일 발사위치(shoot=4.5)와 군사기지(3~7)의 시작점을 비교 => 직전 미사일로 처리된 기지이므로, 무시한다.

직전 미사일 발사위치(shoot=4.5)와 군사기지(4~8)의 시작점을 비교 => 직전 미사일로 처리된 기지이므로, 무시한다.

직전 미사일 발사위치(shoot=4.5)와 군사기지(5~12)의 시작점을 비교

=> 직전 미사일로 처리되지 않은 기지이므로, 새로운 미사일을 발사해야 한다.

직전 미사일 발사위치(shoot=11.5)와 군사기지(11~13)의 시작점을 비교 => 직전 미사일로 처리된 기지이므로, 무시한다.

직전 미사일 발사위치(shoot=11.5)와 군사기지(10~8)의 시작점을 비교 => 직전 미사일로 처리된 기지이므로, 무시한다.

코드

def solution(targets):
    targets.sort(key = lambda it : it[::-1])
    ans, shoot = 0, -0.5
    
    for s, e in targets : 
        if shoot < s : # Was this base intercepted by a previously launched missile??
            ans += 1 # shoot
            shoot = e-0.5 # save shooting location
            
    return ans