[프로그래머스] 단속카메라

링크

https://programmers.co.kr/learn/courses/30/lessons/42884

프로그래머스

풀이

 

모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 되는지를 구하는 문제이다.

 

단속카메라를 가장 적게 설치하려면 차량의 진, 출입 구간이 겹치는 부분이 많아야 된다.

그래서 차량의 진출 구간의 위치가 빠른 순서대로 정렬을 해보았는데

 

어떠한 차량이 진출한 위치 보다 다른 차량의 진입 위치가 더 앞에 있다면 한 개의 단속카메라로 단속을 할 수 있게 된다.

진출 위치로 정렬한 후 A의 진출 위치를 기준 위치로 잡은 후

A의 진출 위치보다 B의 진입 위치가 더 빠르기 때문에 하나의 단속 카메라로 단속이가능하다.

 

하지만 C의 진입 위치는 A의 진출 위치보다 나중에 있기 때문에 단속 카메라의 개수를 증가 시킨 후 C의 진출 위치를 기준으로 한다.

 

D의 진입 위치는 C의 진출 위치보다 앞에 있기 때문에 같은 카메라로 단속이 가능하고

 

E는 C의 진출 위치보다 나중에 있기 때문에 단속 카메라의 갯수를 증가 시킨 후 E의 진출 위치를 기준으로 한다.

 

그러면 단속 카메라의 갯수를 구할 수 있다.

 

 

ps.

priority_queue(이하 pq)는 내림차순으로 정렬이 된다. 이때 오름차순으로 정렬을 하고 싶을 때 물론 함수를 재정의 하여 오름차순으로 정렬할 수 있지만, pq에 push 할 때 입력하는 정수에 (-1)를 곱해주어 pq에 넣어 준다면 오름차순으로 정렬이 되어 사용할 수 있다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

priority_queue<pair<int,int>> pq;
int solution(vector<vector<int>> routes) {
	for (int i = 0; i < routes.size(); i++) {
    	//오름차순으로 정렬하기 위해 -를 붙여줌
		pq.push(make_pair(-routes[i][1], routes[i][0]));
	}

	pair<int, int> start = pq.top(); pq.pop();
	int cnt = 1;
	while (!pq.empty()) {
		pair<int, int> next = pq.top(); pq.pop();

		if (-start.first < next.second) {
			cnt++;
			start = next;
		}
	}
	
	return cnt;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	vector<vector<int>> routes = {
		{-20,15}, {-14,-5},{-18,-13},{-5,-3}
	};

	cout << solution(routes);
}