[Programmers] 프로그래머스 Lv.2 요격 시스템 문제풀이(C++)

끝지점 기준 오름차순 정렬 후,  처음부터 미사일 추가여부 결정하면서 탐색해가기

아이디어 생각이 안나서 답안 참조했었음

#include <string>
#include <vector>
#include<algorithm>
using namespace std;
/*
<문제>
최소 미사일 사용해서 모든 폭격미사일 요격
A나라가 발사한 미사일 - x축에 평행한 직선형태 / 개구간(s, e)
B나라 : 특정 x좌표에서 y축에 수평되도록 미사일 발사, 해당 x좌표 미사일을 관통하여 한번에 요격
 
-> 각 폭격미사일의 x좌표범위목록이 주어질 때, 모든 미사일을 요격하기 위해필요한 요격미사일 수 최솟값을 return하기
 
target<=500000
s<e<=10억
 
<풀이>
 
target을 끝지점 오름차순으로 정렬
  -> 이러면 target 돌면서 시작지점만 보면 됨(끝지점은 이전 target보다 어차피 같거나 지나있으므로)
 
standard = target[0][1]
 
target 처음부터 돌면서, 시작지점만 보기
  if(해당타겟 시작지점 <= standard) -> 시작지점이 끝지점을 넘어서는 순간, 새로운 미사일 추가(아니면 기존 미사일로 요격 가능)
    answer++
    standard = 해당타겟 끝지점
 
끝
 
<시간>
*/
 
bool cmp(vector<int> a, vector<int> b) {
    return a[1] < b[1];
}
 
int solution(vector<vector<int>> targets) {
    int answer = 1;
    sort(targets.begin(), targets.end(), cmp);
    int standard = targets[0][1];
    for (int i = 1; i < targets.size(); i++) {
        if (standard <= targets[i][0]) {
            answer++;
            standard = targets[i][1];
        }
    }
    return answer;
}