내일은 알고리즘

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

스위핑 알고리즘을 통해 풀 수 있는 문제입니다.

스위핑 알고리즘은 입력 데이터를 정렬한 뒤 한 쪽에서부터 쓸어가듯 (Sweep) 풀어가는 풀이를 말합니다.

우리는 모든 미사일을 최소한의 요격으로 처리해야합니다. 이때 하나의 요격으로 여러 미사일을 처리하려면 주어진 미사일의 구간을 동시에 관통해야 합니다. 따라서 미사일을 구간의 시작과 끝으로 정렬 한 후 한 방향으로 탐색하며 가능한 많은 미사일을 요격하도록 요격 위치를 정하면 됩니다.

a < b < c < d인 좌표 a, b, c, d가 있을 때 구간 [a, c]와 구간 [b, d]를 동시에 관통하려면 요격 미사일은 [b, c]를 통과해야 합니다. 이런 식으로 가능한 범위를 좁혀가다 불가능한 경우에 새로운 요격을 쏜다는 로직입니다. 구간을 미리 정렬해뒀기 때문에 왼쪽 좌표는 신경쓰지 않고 오른쪽 좌표만 체크해줘도 같은 결과가 나옵니다.

def solution(targets):
    answer = 1
    targets.sort(key = lambda x : (x[0], x[1]))
    right = targets[0][1]
    
    for idx in range(1, len(targets)):
        if right <= targets[idx][0]:
            right = targets[idx][1]
            answer += 1
            
        else:
            right = min(right, targets[idx][1])
    
    return answer