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

풀이

그리디 알고리즘을 이용하여야 한다.

여러 방법이 있겠으나 우선순위 큐를 이용하여 풀었다.

routes를 첫항을 기준으로 오름차순 정렬하면

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

여기서 [-20,15], [-18,-13], [-14,-5]는 [-14,-13] 범위에서 중복된다.

그러므로 위 세개는 -14, -13 둘 중 하나에서 카메라를 설치하고 -5~-3의 범위에서 카메라를 또 하나 설치한다.

시간이 -30000부터 계속 증가하다가 -20이 되면 [-20, 15]를 만난다. 그럼 [-20, 15]를 우선순위 큐에 넣는다.

우선순위 큐는 현재 고속도로에 존재하는 차들이며 고속도로에서 나가는 시간의 최소힙을 기준으로 한다.

시간이 또 증가하다가 -18이 되면 [-18, -13]을 만나서 역시 우선순위 큐에 넣는다.

마찬가지로 시간이 -14가 되면 [-14, -5]을 넣는다.

그리고 또 시간이 증가하여 -13이 되었다.

현재 우선순위 큐의 top은 [-18, -13]인데 이 차는 고속도로에서 나가야하므로 -13에서 카메라를 설치한다.

그리고 현재 큐에 있는 차들은 모두 -13에서 카메라를 만날 수 있으므로 큐를 모두 비워준다.

큐가 비워진채로 시간이 또 증가하여 -5가 되면 [-5,-3]을 큐에 넣는다.

시간이 -3이 되면 [-5,-3]을 만나서 카메라를 설치하고 큐를 비운다.

모든 차가 고속도로를 탈출했으므로 최종적으로 설치된 카메라는 두대다.

while (idx < size || !q.empty()) {
	while (idx < size && time == routes[idx][0]) { // 차가 고속도로에 진입
		q.push(routes[idx][1]); // 해당 차를 큐에 넣는다.
		idx++; // 다음 차를 선택하기 위한 인덱스
	}

	if (!q.empty() && q.top() == time) { // 차가 고속도로에서 나감
		while (!q.empty()) { // 큐를 비워준다.
			q.pop();
		}
		answer++; // 카메라 설치
	}
	time++;
}

디버깅

반례

routes : [[-30000, 30000], [-4000, 4000], [-4000, 4000]]

차가 고속도로에 진입하면 다음 차를 선택했는데, 동일한 시간에 여러대의 차가 고속도로에 진입하는 경우가 있음.

반복문을 이용해서 모든 차가 고속도로에 진입 후 다음 차를 선택하도록 수정

수정 전

if (idx < size && time == routes[idx][0]) {
	q.push(routes[idx][1]);
	idx++;
}

수정 후

while (idx < size && time == routes[idx][0]) {
	q.push(routes[idx][1]);
	idx++;
}

구현

// c++

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end());
    priority_queue<int, vector<int>, greater<int>>q;
    int idx = 0;
    int size = routes.size();
    int time = routes[0][0];
    
    while(idx < size || !q.empty()){
        while(idx<size && time == routes[idx][0]){
            q.push(routes[idx][1]);
            idx++;
        }
        
        if(!q.empty() && q.top() == time){
            while(!q.empty()){
                q.pop();
            }
            answer++;
            cout<<time<<endl;
        }
        time++;
    }
    return answer;
}