요격 시스템

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

프로그래머스

 

I. 문제 개요

미사일은 최소로 발사해야 하니까, 가장 많이 겹치는 구간에 발사하는 방향으로 알고리즘을 설계해야 한다.

 

II. 알고리즘 및 풀이

여기에서는 그리디 알고리즘과 정렬을 사용한다.

 

그리디 알고리즘은 현재 상황에서 최선의 선택을 하는 알고리즘이다.

 

1. 정렬

targets.sort(key = lambda x: x[1])

st = 0
ed = 0

 

주어진 폭격미사일들의 끝 구간을 기준으로, 오름차순으로 정렬한다.

 

그러면 끝점을 기준으로, 미사일을 발사할 지 여부를 뒤에서 결정할 수 있다.

 

st, ed 는 구간이 겹치지 않은 폭격미사일의 시작점, 끝점을 담는 변수이다.

 

2. 그리디 탐색

for i in range(len(targets)):
    tgt = targets[i]
    
    if tgt[0] >= ed:    # 현재 폭격미사일의 구간과, 이전에 본 폭격미사일의 구간이 안겹친다면
        ans += 1        # 요격미사일 발사
        ed = tgt[1]     # 현재 보는 폭격미사일 구간의 끝점으로 변경
        # st = tgt[0]
        
return ans

 

이전에 본 폭격 미사일의  끝점(ed)과, 지금 보는 폭격미사일의 시작점(tgt[0])을 비교한다.

 

만약 ed > tgt[0] 이 성립하면, 이전 폭격미사일과 현재 폭격미사일은 구간이 겹치므로, 요격미사일을 별도로 발사하지 않아도 된다.

 

반대로 ed <= tgt[0] 인 경우, 구간이 겹치지 않기에 요격미사일을 한발 더 쏴야 한다.

 

III. 전체 풀이코드

def solution(targets):
    ans = 0
    targets.sort(key = lambda x: x[1])
    
    st = 0
    ed = 0
    
    for i in range(len(targets)):
        tgt = targets[i]
        if tgt[0] >= ed:
            ans += 1
            ed = tgt[1]
            # st = tgt[0]
    
    return ans

 

IV. 결과