프린터(Level2)

• 문제 링크: 코딩테스트 연습 > 스택/큐 > 프린터

• 문제 이해

  1. 인쇄 대기목록에 있는 문서를 출력하되, 중요도가 높은 문서를 먼저 인쇄합니다.
  2. 중요도가 가장 높은 문서가 나타나기 전 문서들은 계속해서 가장 뒤로 보냅니다.
  3. 저는 문서를 뒤에 보낸다기 보다는, 시작점을 바꾸는 방향으로 생각해보았습니다.
  4. 예를들어, priorities의 크기가 4이고, 중요도가 가장 높은 문서가 priorities[2]면,
     [2]출력 후, [3]->[1]->[2]로 순회하며 최댓값을 찾는 식으로 생각했습니다.

• 알고리즘 구현

  1. 기본적인 아이디어는 앞서 언급한 것처럼, 처음에는 0번째 인덱스부터 시작하여 우선순위
     최댓값을 찾고, 최댓값의 index를 vector에 담습니다.
  2. 담은 index는 이제 볼 필요가 없으므로, 우선순위는 가장 낮은 -1로 설정 후, 그 index
     다음부터 index 이전까지 한바퀴 순회하며 새로운 최댓값을 구합니다.
  3. 이때, priorities의 크기가 4이면, 한바퀴 순회할 때 4번 봐야하므로, turn=n을 줄여
     나가는 방식, i는 증가시키되 i%n하여 index를 넘어가면 처음으로 오는 방식으로 합니다.
  4. 과정을 반복하며, 구해진 최댓값을 vector에 계속해서 담습니다.

• 알고리즘

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> priorities, int location) {
    int n = priorities.size();
    vector<int> printQueue;
    int i = 0;
    while (printQueue.size() != n) {
    	int maxPriority = -1, maxPriorityIdx = 0;
        int turn = n;
   		while (turn--) {
            i = i % n;
    		if (priorities[i] > maxPriority) {
            	maxPriority = priorities[i];
            	maxPriorityIdx = i;
        	} 
            ++i;
    	}
        if (location == maxPriorityIdx)
            return (printQueue.size() + 1);
    	printQueue.push_back(maxPriorityIdx);
    	priorities[maxPriorityIdx] = -1;
    	i = maxPriorityIdx;
    }
    return (-1);
}