[프로그래머스] [C++] 프린터

문제 풀이

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location) {
	int answer = 0;
    // 고유번호와 우선순위 값을 받기 위해 pair로 설정
	queue<pair<int, int>> q;
    // 우선순위 큐. 내림차순으로 자동 정렬된다.
	priority_queue<int> pq;
	
    // q를 만들어 고유번호와 우선순위 값을 넣고 우선순위 큐인 pq에 넣는다.
	for (int i = 0; i < priorities.size(); i++) {
		q.push(make_pair(i, priorities[i]));
		pq.push(priorities[i]);
	}

	// q가 빌 때까지
	while (!q.empty()) {
    	// q의 맨 앞의 우선순위 값이 pq의 맨 앞, 즉 최댓값과 같다면
		if (q.front().second == pq.top()) {
        	// 그리고 해당 최댓값의 고유번호가 찾고자 하는 location과 일치한다면
			if (q.front().first == location) {
            	// 몇 번째인지를 찾는 것이므로 +1 을 해서 리턴
				return ++answer;
			}
            
            // 최댓값은 같으나 고유번호가 일치하지 않는다면
			else {
            	// 대기 시간을 추가하고 q와 pq의 맨 앞(top)을 제거한다
				answer++;
				q.pop();
				pq.pop();
			}
		}
        
        // q의 맨 앞의 우선순위 값이 최댓값이 아니라면
		else {
        	// q의 맨 앞을 맨 뒤로 넣고
			q.push(q.front());
            // 맨 앞은 뒤에 넣어줬으니 pop 해준다
			q.pop();
		}
	}
    return answer;
}

---

사용 알고리즘 간략 소개

 

1. 우선순위 큐(priority queue)

include<queue>

priority_queue <데이터 타입> 변수명;

- 힙 연산을 사용하기 때문에 정렬 시 효율성이 좋다.

- 우선순위 큐에 데이터를 집어넣으면 기본적으로 내림차순(less<>)으로 정렬된다.

- 오름차순으로 정렬하고 싶다면 <> 안쪽 맨 뒤에 greater<데이터 타입>을 추가하면 된다.

     ex) priority_queue<int, vector<int>, greater<int>> pq

 

---

문제 링크

 

 

programmers.co.kr/learn/courses/30/lessons/42587?language=cpp

코딩테스트 연습 - 프린터