Taxol

I’ve always been.

스택 - 프린터

Updated:

C++

스택/큐 - 프린터

문제

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

문제 출처

접근 방법

각 문서의 우선 순위와, 처음 주어진 문서 들의 순서를 함께 저장하는 queue를 선언한다.
queue의 특징에 맞게 제일 앞의 문서를 꺼낸 후, 그 문서의 우선 순위가 나머지 문서들의 우선 순위보다 더 크면 인쇄를 하고, 뒤에 밀린 문서들의 우선 순위보다 작을 시에는 현재 대기 queue의 제일 뒤에 push한다.
인쇄를 하는 중 만약 그 문서의 순서가 처음 주어진 location과 같으면 몇번째로 출력하였는지도 알린다.

구현

우선순위와 현재 순서를 pair로 묶은 후, 이를 queue를 통해 모두 저장한다.
이 queue가 empty가 될 때까지, 즉 모든 문서가 인쇄 될때까지 while문을 돌린다.
제일 앞의 문서의 우선순위와 처음 순서를 pop 한 후, 뒤의 대기 문서들의 우선순위와 다 비교한다.
queue는 순회가 되지 않으므로, 미리 size를 가지고 이 size 만큼 queue를 하나씩 뽑아 비교하고 다시 넣는 방식으로 우선 순위를 비교한다.
만약 순회 도중 우선 순위가 밀리면, isSamll을 true로 해주어 이 문서는 프린트를 할 수 없다는 것을 명시해준다.

이후 조건문 3가지로 문서의 처우를 결정한다.

  1. isSmall이 true이어, 우선순위가 밀리면 기존 queue(대기 목록)의 제일 뒤에 저장한다.
  2. isSmall이 false이며, 이는 우선순위가 제일 큰 문서라는 뜻이다. 따라서 인쇄를 하는데, 만약 이 문서의 처음 순서가 주어진 매개변수 location과 같으면 현재 출력 순서를 저장하여 결과 값을 도출해 낸다.
  3. isSmall이 false이며, 순서가 처음 의도한 순서와 다른 경우이다. 이 경우에는 출력 순서를 증가시켜준다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int order = 1;
    queue<pair<int,int>> qe;            //문서의 우선 순위와 초기 순서 등 정보가 들어있는 queue
    for (int i = 0; i < priorities.size(); i++) {
        qe.push(make_pair(priorities.at(i), i));
    }
    while (!qe.empty()) {
        int front = qe.front().first;           //제일 앞의 문서의 정보를 꺼낸다.
        int curlo = qe.front().second;
        qe.pop();
        int size = qe.size();
        bool isSmall = false;
        while (size--) {                        //문서 대기 목록들의 정보를 비교한다.
            int comp = qe.front().first;
            int complo = qe.front().second;
            qe.pop();
            if (front < comp)
                isSmall = true;
            qe.push(make_pair(comp, complo));
        }

        if (isSmall) {                          //우선 순위가 밀렸을 경우
            qe.push(make_pair(front, curlo));
        }
        else if(curlo == location){             //우선 순위가 제일 높고, 주어진 위치의 문서일 경우
            answer = order;
        }
        else {                                  //우선 순위가 제일 높지만, 필요한 위치의 문서가 아닌 경우
            order++;
        }
        isSmall = false;
    }
    
    return answer;
}

후기 및 개선할 점

20분 컷. 이전 과는 다르게 pair를 사용하여 더 간결하게, 쉽게 해결하였다.

You may also enjoy