[Programmers] Q181188 요격 시스템

[Programmers] Q181188 요격 시스템

Question

Language: Python

해당 문제는 단속카메라문제와 비슷한 유형의 문제로, 최소한의 로켓을 활용하여 모든 미사일들을 요격하는 방법을 구하는 문제이다.

이 문제에서 주목해야될 점은 각 로켓들이 발사되는 위치는 미사일의 시작 혹은 끝점이다. 그 중에서도 끝점에 설치해야된다. 시작점에 설치하게 되면 해당 미사일만 요격되게 되므로 최소 로켓이 될 수 없다. 따라서, 끝점에서 발사되게끔하여 다른 미사일도 같이 요격될 수 있게끔한다. 즉, 끝점을 기준으로 탐색을 진행해야한다.

또한, 끝점을 기준으로 정렬하여, 먼저 통과하는 미사일을 기준으로 로켓을 발사하게끔하여 다른 미사일도 같이 요격될 수 있도록 한다. 출발점을 기준으로 정렬을 수행하면 나중에 출발한 미사일을 놓치는 경우가 발생한다.

Solution

def solution(targets):
    missile_count=0
    missile_location=-0.1
    #끝점을 기준으로 정렬 수행
    targets.sort(key=lambda x: x[1])
    
    for s,e in targets:
        #발사되는 로켓이 미사일 보다 이전이라면 겹치지 않기 때문에 현재 로켓으로는 요격이 불가능하므로 새로운 로켓을 추가한다.
        if missile_location < s:
            missile_count+=1
            #개구간에서 발사 되므로 끝점 앞칸에서 발사되도록 한다.
            missile_location=e-1
        
    return missile_count