프로그래머스 요격 시스템 - C++ 풀이

---

 

1. 타겟들을 끝점 기준으로 오름차순 정렬한다.
2. 순차적으로 끝점에서 요격한다.
3. 만약 현재 타겟의 (시작점 > 마지막 요격점)인 경우, 새로 요격해야 한다.

 

1. 타겟들을 끝점 기준으로 오름차순 정렬한다.

 먼저 타겟들을 끝점 기준으로 오름차순 정렬한다. 끝점의 x좌표가 작은 순서대로 처리하기 위함이다.

 

2. 순차적으로 끝점에서 요격한다.

 요격 횟수를 최소화해야 하므로 한 번의 요격으로 최대한 많은 타겟을 처리해야 한다. 따라서 타겟의 최대한 끝점에서 요격해야 뒤에 있는 타겟들에 최대한 많이 걸칠 수 있다. 마지막 요격점은 기록해둔다.

 

3. 만약 현재 타겟의 (시작점 > 마지막 요격점)인 경우, 새로 요격해야 한다.

 만약 현재 타겟의 시작점이 마지막 요격점보다 뒤에 있는 경우 요격 포인트안에 들어오지 않으므로 새로 요격해야 한다. 새로운 타겟도 역시 끝점에서 요격해줄 것이므로 마지막 요격점을 현재 타겟의 끝점으로 업데이트해준다.

---

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

typedef pair<int, int> pii;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    int n = targets.size();
    int currentPoint = 0;
    vector<pii> targetPairs;
    
    for (auto target: targets) {
        targetPairs.push_back({target[1], target[0]});
    }
    
    // 끝점 기준으로 오름차순
    sort(targetPairs.begin(), targetPairs.end());
    
    // 항상 끝점에서 요격
    for (auto targetPair: targetPairs) {
        // 기존 요격 포인트안에 들어오지 않음 -> 새로 요격
        if (targetPair.second >= currentPoint) {
            answer++;
            currentPoint = targetPair.first;
        }
    }
    
    return answer;
}