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

문제

프로그래머스

 

풀이

이 문제는 (s, e) 좌표로 떨어지는 폭격 미사일들을 최소한의 요격 미사일로 막아야하는 문제이다.

 

문제 설명

1. 2차원 공간에서 x축에 평행한 선분으로 표현되는 폭격 미사일들을 최소한의 요격 미사일로 모두 요격해야 한다.
2. 요격 미사일은 특정 x 좌표에서 발사되어 해당 좌표를 지나는 모든 폭격 미사일을 동시에 요격할 수 있으며, 이를 통해 모든 폭격 미사일을 요격하는 데 필요한 최소 요격 미사일 수를 구해야 한다.

문제 풀이

1. targets의 요소들을 s 축 기준으로 오름 차순 정렬 한다.
2. targets 요소들을 순차적으로 탐색하여 end 변수에 e 값의 최솟값을 저장한다.
3. 저장된 end 값이 탐색한 s 값보다 작거나 같을 경우, 요격 미사일을 배치한 후, e 값을 최신화한다.
4. 탐색이 종료 된 후, 남은 마지막 폭격 미사일을 제거 해야하기 때문에 answer에 + 1을 한 후 return한다.

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

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    
    sort(targets.begin(), targets.end());
    
    int end = 987654321;
     
    for(int i = 0; i < targets.size(); i++){
        if(end > targets[i][1]){
            end = targets[i][1];
        }
        else if(end <= targets[i][0]  ){
            answer ++;
            end = targets[i][1];
        }
    }
    
    return ++answer;
}