프로그래머스 요격 시스템

문제 바로가기
level2 (23.04.25 기준)

✏ 생각하기

입력 크기가 500,000개다. 충분히 하나씩 다 볼 수 있다.
우선 sorting을 하는 것이 좋을 것이다. 모든 미사일을 요격해야 하므로, 특정 기준으로 정렬 후 하나씩 요격 가능한 경우를 생각한다면 문제에서 원하는, '모든 미사일을 요격'이라는 조건을 만족할 수 있다.
그렇다면 sorting 기준은? 1순위는 e, 2순위는 s로 두어 오름차순 정렬 한 후 e-1 < x < e 인 좌표 x를 요격 좌표로 생각해보자. (x는 정수가 아닐 수 있다) 그러면 현재 미사일 i를 요격시키면서 가능한한 많은 미사일들을 요격할 수 있다. 만약 요격 좌표 x를 x'(<=e-1)로 교체할 경우, 요격 가능한 미사일 수가 감소함을 쉽게 알 수 있다.
start기준으로 한다면?
모든 경우를 보지 않고 sorting한 후 e-1가 요격 좌표인 경우만 생각하기에 greedy 문제라 볼 수 있다.

📒 알고리즘

1. targets를 e, s 기준으로 sorting한다.
2. i번째 미사일의 s, e를 각각 s_i, e_i라 하고, 초기값이 i+1인 j에 대해,
   2-1. targets[j][0](==s_j) 가 e_i 이상이면 필요한 요격 미사일 수(answer) += 1. i번째 폭격 미사일을 요격할 미사일로는 이러한 j번째 미사일 동시 요격이 불가능하기 때문이다.
   2-2. s_j가 e_i 보다 작을 경우 j+=1, 즉 다음 폭격 미사일에 대해 살펴본다.
3. return answer

💻 코드

위 알고리즘을 토대로 처음 제출한 코드는 아래와 같다.

def solution(targets):  # 500,000개 이하, 범위는 100,000,000
    # targets를 end 기준 sorting
    targets.sort(key=lambda x:(x[1], x[0]))
    # end_i 에 대해 start_j < end_i 인 모든 미사일들 요격 가능 -> 그리디
    # 위 방식에 따라 targets 들에 대해 모두 살펴보기
    answer = 0
    i = 0
    while i < len(targets): 
        s_i, e_i = targets[i]
        j = i+1
        while j < len(targets) and targets[j][0] < e_i: 
            j += 1
        answer += 1
        i = j
    return answer