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

프로그래머스

 

 

입출력 예

 

 

• 겹치는 구간에 있는 미사일은 하나의 미사일로 전부 요격 가능. 개구간(s, e)의 미사일은 s와 e에서 발사된 요격 미사일로 요격 불가

 

> 일단 주어지는 targets 배열을 오름차순으로 정렬

> 이후 현재 타겟의 e보다 s가 작은 타겟들을 전부 패스

> 현재 타겟의 e보다 e가 작은 타겟이 나올 시 요격 미사일 수 값을 증가 시키고 e 값을 다음 타겟의 e 값으로 갱신

 

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

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    
    // 배열을 오름차순으로 정렬
    sort(targets.begin(), targets.end());
    
    for(int i = 0; i < targets.size();) {
    	// 현재 타겟의 e 값을 저장
        int end = targets[i++][1];
        answer++;
        
        // 다음 타겟의 s가 현재 타겟의 e보다 작다면 반복
        for(; i < targets.size() && targets[i][0] < end;) {
        	//다음 타겟의 e가 현재 타겟의 e보다 작다면 e를 갱신
            if(targets[i][1] < end) end = targets[i][1];
            i++;
        }
    }
    
    return answer;
}