[알고리즘] 프린터

포인트

• 힙은 자료구조 우선 순위 큐는 그것을 구현한 것
• 적절한 힙의 사용은 너무나 좋다.

c++/cpp

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    priority_queue<int> pq; //max heap
    //priority_queue<int, greater<>()> pq; //min heap
    queue<pair<int, int>> q;

    int size = priorities.size();
    for (int i = 0; i < size; i++) {
        q.push(make_pair(i, priorities[i])); // 문서 번호와 중요도
        pq.push(priorities[i]); // 중요도 자동으로 중요도 순으로
    }

    while (!q.empty()) {
        int target, p;
        tie(target, p) = q.front(); // tuple 라이브러를 사용하면 코드가 깔끔
        q.pop();
        // 중요도 제일 큰지 확인
        if (p == pq.top()) {
            pq.pop();
            answer++;

            if (target == location)  //현재 문서가 내가 인쇄를 요청한 문서다
                break;

        } else {
            //다시 큐에 넣는다.
            q.push(make_pair(target, p));
        }
    }

    return answer;
}

python

from collections import deque


def solution(priorities: list, location: int) -> int:
    answer = 0
    dq = deque([(value, index) for index, value in enumerate(priorities)])
    # dq로 로테이션을 돌 수 있다. 
    while dq:
        val, idx = dq[0]  # 앞에 있는 친구를 꺼내서
        if dq and max(dq)[0] > val:  # 값을 확인하고
            dq.rotate(-1)  # 아니면 다시 뒤로 넣어준다.
        else:  # 맞으면 1개 증가
            answer += 1
            if idx == location:  # 위치가 맞으면 답을 출력
                break

    return answer