[프로그래머스/알고리즘] 단속카메라

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

입출력 예

routes : [[-20,15], [-14,-5], [-18,-13], [-5,-3]]

return : 2

해결 방법

저는 우선순위 큐에서 가장 첫번째로 진출되는 순간에 단속카메라를 설치하는 방식으로 했습니다. 

처음에 routes를 진입 지점을 기준으로 정렬 합니다. 입출력 예를 들면

[[-20,15],  [-18,-13], [-14,-5], [-5,-3]]

이런 순이 됩니다.

그리고 임의의 변수(current)를 만들어서 가장 진입 지점이 적은 -20을 저장합니다. 

우선순위 큐를 이용해서 진입 지점이 current일 경우의 route를 우선순위 큐에 저장합니다.

우선순위 큐는 진출 지점을 오름차순으로 만들어야 합니다.

그리고 current를 1개씩 증가하면서 우선순위큐의 값이 진출되는 순간에 단속카메라 1개를 설치하고 우선순위 큐를 비워줍니다.

그리고 그 다음 route를 가져와서 current도 그 다음 값의 진입 지점으로 바꿔주고 위와 같이 반복해주면 결과가 나옵니다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;

struct Pred {
	bool operator()(vector<int> a, vector<int> b) {
		return a[0] < b[0];
	}
};
struct Pred1 {
	bool operator()(int a, int b) {
		return a > b;
	}
};
int solution(vector<vector<int>> routes) {
	int answer = 0;
	int current;
	int i = 1;
	sort(routes.begin(), routes.end(), Pred());
	priority_queue<int, deque<int>,Pred1> prique;
	current = routes[0][0];
	prique.push(routes[0][1]);
	while (!prique.empty()) {
		while (i!=routes.size()) {
			if (routes[i][0] == current) {
				prique.push(routes[i][1]);
				i++;
			}
			else
				break;
		}
		if (current == prique.top()) {
			while (!prique.empty()) {
				prique.pop();
			}
			if (i != routes.size()) {
				prique.push(routes[i][1]);
				current = routes[i][0];
			}
			else {
				answer++;
				break;
			}
			answer++;
		}
		else current++;
	}
	return answer;
}