[C++] 요격 시스템

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
bool cmp(vector<int> a, vector<int> b) {
    if(a[0] == b[0]) {
        return a[1] < b[1];
    }
    return a[0] < b[0];
}
 
int solution(vector<vector<int>> targets) {                                                            
    int answer = 1;
    
    sort(targets.begin(), targets.end(), cmp);
    int now = targets[0][1];
    int max_tmp = targets[0][1];
    
    for(int i=1; i<targets.size(); i++) {
        if(targets[i][0] >= now) {
            answer += 1;
            now = targets[i][1];
        }
        else { now = min(now, targets[i][1]); }
    }
    
    return answer;
}

 

 

혼자 테스트케이스 잘못짜서 30분 잘못 쓴 문제

 

• target의 길이 최대 500,000

최대 50만이므로 target 의 시작과 끝점을 1씩 더해주는 방식으로 하게되면 무조건 시간초과가 난다.

 

그렇기때문에 O(n) 혹은 O(nlogn) 으로 처리해야한다.

 

구간의 첫번째를 기준으로 오름차순 정렬하고 아닐 경우 두번째를 기준으로 오름차순 정렬 하게 sort 함수를 커스텀했다.

(C++ 내장 라이브러리 sort 함수는 시간복잡도가 O(nlogn) 이므로 입력값에 의해 시간초과가 날 일은 없으니 걱정말자.)

 

이후 끝점의 최솟값을 갱신하며 끝점의 최솟값보다 클 경우 미사일이 더 필요한 것이므로 answer를 더해주고 최솟값을 갱신해주는 방식으로 해결했다.