[프로그래머스][C++] 요격 시스템

요격 시스템

문제 링크

요격 시스템

분석

적의 미사일이 N개 발사되고, 각 미사일은 x좌표를 특정 구간 [s, e]를 따라 이동합니다.

요격 시스템은 x좌표 하나를 지정하여 해당 좌표를 지나가는 미사일을 한 번에 모두 요격할 수 있습니다.

모든 미사일을 요격할 때 필요한 최소 횟수를 구해야 합니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    
    // 미사일 종료 좌표를 기준으로 오름차순 정렬한다.
    sort(targets.begin(), targets.end(), [](const vector<int>& a, const vector<int>& b)
         {
            return a[1] < b[1];
         });
    
    // 마지막으로 요격한 지점의 x 좌표
    int lastXCorrdinate = 0;
    
    // 모든 미사일 구간을 순회하며 요격 여부를 판단
    for (const auto & target : targets)
    {
        int start = target[0];
        int end = target[1];
        
        // 현재 미사일이 이전 요격 지점으로는 요격되지 않는 경우
        if (lastXCorrdinate <= start)
        {
            ++answer;
            
            lastXCorrdinate = end;
        }
    }
    
    return answer;
}

각 미사일의 구간 [s, e]에서 e를 종료 지점으로 보아 기준을 두고, 오름차순 정렬해주었습니다.
해당 종료 지점이 가장 일찍 끝나는 구간부터 선택해주어, 종료 지점을 기준으로 요격해줍니다.
이후 순회하는 구간의 시작점보다 최근에 발사한 요격 지점의 위치 값이 작다면 이미 요격 된 상태이므로 넘어갑니다.
만약, 최근에 발사한 요격 지점의 위치 값이 크거나 같다면 요격되지 않는 상태이므로, 새로운 요격을 추가합니다.

성능 요약

시간 복잡도는 $O(n \ log \ n)$입니다.

• 정렬 $O(n \ log \ n)$
• 모든 미사일 구간을 순회하며 요격 여부를 판단하는 반복문 $O(n)$
• $O(n \ log \ n) + O(n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.02ms, 4.22MB)
테스트 4 〉 통과 (0.11ms, 3.82MB)
테스트 5 〉 통과 (1.37ms, 5.15MB)
테스트 6 〉 통과 (16.04ms, 22.1MB)
테스트 7 〉 통과 (103.82ms, 96.8MB)
테스트 8 〉 통과 (131.80ms, 96.8MB)
테스트 9 〉 통과 (130.38ms, 94.6MB)
테스트 10 〉 통과 (36.65ms, 78MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)