[L3] 프로그래머스 단속카메라 C++ 우선순위 큐, 그리디 알고리즘

리뷰

프로그래머스

 

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

우선순위 큐를 두개 사용하여 문제를 해결했다.

 

 

전역 변수

• Wait : 아직 고속도로에 진입하지 않은 차량의 정보를 담을 구조체, 진입 지점을 기준으로 오름차순 정렬
• Ing : 고속도로에 주행중인 차량의 정보를 담을 구조체, 진출 지점을 기준으로 오름차순 정렬

 

함수

없음

 

 

문제풀이

1. 정수형 변수 n에 routes의 size를 초기화 해준다.
2. Wait, Ing 구조체 타입의 우선순위 큐 pq1, pq2를 초기화 해준다.
3. pq1에 routes에 존재하는 진입, 진출 지점 정보를 추가해 준다.
4. cur을 진입 지점의 최소값인 -30000으로 초기화 하고, pq1, pq2가 모두 빌때까지 반복문을 수행한다.
5. pq1이 비지 않았으면서 진입 지점이 cur보다 작거나 같은 요소들을 pq2로 옮겨준다.
6. pq2가 비지 않았다면 cur을 pq2의 top요소의 진출 지점으로 초기화 해주고, answer을 증가시킨다.
7. pq2가 비지 않았고, 진입 지점이 cur보다 작거나 같으면 pq2에서 제외해준다.
8. 만약 pq1이 비지 않았다면 cur을 pq1의 진출 시점으로 업데이트 한다.
9. 모든 반복문을 수행한 후에 answer에 저장된 값을 리턴해 준다.

 

참고 사항

pq2에서 cur을 업데이트 해주는 것은, pq1은 모두 비었는데 pq2에 요소가 남아있을 때를 대비한 것이다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

struct Wait {
    int it, ot;
    bool operator<(const Wait& other) const {
        return it > other.it;
    }
};

struct Ing {
    int it, ot;
    bool operator<(const Ing& other) const {
        return ot > other.ot;
    }
};

int solution(vector<vector<int>> routes) {
    int answer = 0;
    int n = routes.size();
    
    priority_queue<Wait> pq1;
    priority_queue<Ing> pq2;
    for (vector<int> i : routes) pq1.push({i[0], i[1]});
    
    int cur = -30000;
    while (!pq1.empty() || !pq2.empty()) {
        while (!pq1.empty() && pq1.top().it <= cur) {
            Wait wait = pq1.top(); pq1.pop();
            pq2.push({wait.it, wait.ot});
        }

        if (!pq2.empty()) {
            cur = pq2.top().ot;
            answer++;
        }
        
        while (!pq2.empty() && pq2.top().it <= cur) pq2.pop();
        
        if (!pq1.empty()) cur = pq1.top().ot;
    }
    return answer;
}