[프로그래머스] Level 2 : 요격 시스템

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

1. 미사일을 e를 기준으로 오름차순으로 정렬한다.

• 이미 요격된 미사일을 고려하기 위해 가장 짧은 미사일부터 요격을 시작한다.

2. 요격을 할 때마다 요격한 지점의 위치를 저장한다. 시작은 0

3. 미사일의 s가 요격 지점보다 크면, 미사일의 s 지점에 요격을 가한다.

• s지점을 요격 지점으로 새로 할당한다.
• 매번 요격한 미사일의 s지점을 요격 지점으로 정하기 때문에, 이보다 작은 요격 지점은 존재하지 않는다.

 

요격한 미사일의 끝 지점(e)를 요격 지점으로 계속 초기화

#include <vector>
#include <algorithm>
using namespace std;

struct Cmp
{
	bool operator()(vector<int>& a, vector<int>& b) { return a[1] < b[1]; }
};

int solution(vector<vector<int>> targets) {
	int answer = 0, Shot = 0;

	sort(targets.begin(), targets.end(), Cmp());

	for (const auto& target : targets)
	{
		if (target[0] < Shot) continue;
		Shot = target[1];
		answer++;
	}
	return answer;
}