[프로그래머스 lv2] 프린터 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

문서를 순서대로 출력하되, 가장 앞에 있는 문서의 뒤쪽에 우선순위가 더 높은 문서가 있다면 현재 문서를 제일 뒤로 보내야 한다.

특별한 방법 필요없이, 문제에서 요구한 그대로 구현하면 정답을 받을 수 있다.

 

일단, 문서들의 초기 위치와 우선순위의 정보를 큐에 pair 형태로 저장해놓고,

해당 큐에서 하나씩 문서를 꺼내면서(프린트) location으로 주어진 문서가 몇번째로 프린트 되는지 확인하면 된다.

 

하나씩 문서를 꺼낼 때는, 큐의 가장 앞에 있는 문서가 남아있는 문서들 중에서 가장 높은 우선순위를 갖는지 확인하되,

가장 높은 우선순위를 갖지 않는다면 이를 큐의 가장 끝으로 보낸다. 

반복해서 문서들을 뒤로 보내다가, 가장 높은 우선순위를 갖는 문서가 제일 앞에 있으면 이를 큐에서 꺼내면 된다.

 

그렇다면, 큐의 가장 앞에 있는 문서가 가장 높은 우선순위를 지니는지 어떻게 확인할 수 있을까?

priorities 배열을 내림차순으로 정렬하고, 하나를 꺼낼 때마다 idx를 1개씩 증가시키면 다음으로 꺼내야 할 가장 높은 우선순위의 문서를 확인할 수 있다.

 

꺼낸 문서의 초기 위치가 location이라면 현재까지 꺼낸 문서의 수 cnt를 리턴한다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

#define X first
#define Y second

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int solution(vector<int> priorities, int location) {
    
    queue<ii> q;
    for (int i=0; i<priorities.size(); i++) 
        q.push({i, priorities[i]});
    sort(priorities.begin(), priorities.end(), greater<>());
    
    int cnt = 0;
    int idx = 0;
    while (true) {
        cnt++;
        while (!q.empty() && q.front().Y != priorities[idx]) {
            q.push(q.front());
            q.pop();
        }
        if (q.front().X == location) break;
        q.pop();
        idx++;
    }
    return cnt;
}