뚝딱뚝딱

요격 시스템

요격 시스템 문제는 먼저 sorting을 해주어야 한다.

이 때 어느 값을 기준으로 정렬할 것인지가 관건이 되는데..

주어진 예제에서 어떤 폭격 미사일 하나의 구간만을 고려한다고 해보자.

 예를 들면 4-5 구간의 미사일만을 고려해 보자.

4를 요격 범위의 start로 S, 5를 요격 범위의 end로 E라고 표현하고, 현재의 요격 범위로 두자.

end가 4(현재의 S)보다 작은 미사일의 경우, 현재의 요격 범위에 포함될 수 없다.

따라서 start가 5(현재의 E)보다 큰 미사일의 경우에도 현재의 요격 범위에 포함될 수 없다.

그러므로 요격 범위에 들어올 자격이 되는지는, 각 미사일 구간의 end 포인트 지점에 달려있다.

따라서 end를 기준으로 오름차순 정렬해준다.

end를 기준으로 오름차순 정렬해주면

[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4] → [1,4], [4,5], [3,7], [4,8], [5,12], [11,13], [10,14]
이 된다.

미사일을 어차피 한번이상 쏘게 되어 있으니까, count는 1로 시작한다.

처음 요격 구간을 [1,4]로 설정하고 그 다음 구간부터 차례로 순회한다.

첫 S=1, E=4가 된다.

다음 미사일의 범위가 [4,5]이고, 이것의 시작 지점인 4가 현재 요격 구간의 E보다 작아야 한번에 쏠 수 있다.
(엔드 포인트인 4에서는 쏘지 못한다. 조건에 명시되어 있다.)

그런데 E보다 작지 않기 때문에 이 구간에는 첫번째 미사일 구간 빼고는 더이상 요격할 미사일이 없는 것이다.

따라서 count를 1올려주고, 다음 미사일 구간의 시작점을 s로, 끝점을 e로 하여 새로운 요격 범위를 갱신하고 위 과정을 반복하도록 한다.

그럼 최종 요격 발사 횟수를 COUNT를 반환함으로써 얻을 수 있다.

C++로 해결한 코드는 아래와 같다.

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

using namespace std;

bool cmp(vector<int> &v1, vector<int> &v2) {
	if (v1[1] == v2[1])
		return v1[0] < v2[0];
	else return v1[1] < v2[1];
}

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

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

	int e = targets[0][1];

	answer++;

	for (int i = 1; i < targets.size(); i++) {
		if (targets[i][0] < e) {
			continue;
		}
		else {
			answer++;
			e = targets[i][1];
		}

	}

	return answer;
}