[백준] 1966번 프린터 큐

주어진 조건에 따라 프린터 큐를 구현하는 문제이다. 우선순위를 구현하는 것이 포인트

문제

---

힌트

문제에서 우선순위가 낮은 경우에 뒤로 돌아가서 다시 순서를 기다리도록 한다고 했다. 이 때문에 우선순위가 같은 경우에는 순서가 바뀔수 있다.

문제에서 내가 찾고 있는 순서의 인쇄 순서를 어떻게 표시할수 있을까를 생각하는 것이 좋다.

구조체나 class를 활용하는 것보다 좋은 방법이 있다. 필자의 경우 잘못된 방식에서 벗어나지 못해서 풀이시간이 오래걸렸다.

코드 자세히 보기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, int index)
{
 vector<int> que(n, 0);
 vector<int> priority;
 int answer = 0;
 int count = 0;
 for (int i = 0; i < n; i++)
  cin >> que[i];
 priority = que;
 sort(priority.begin(), priority.end());
 while (1)
 {
  if (que[count] < priority.back())
  {
   que.push_back(que[count]);
   if (index == count)
    index = que.size() - 1;
  }
  else if (que[count] == priority.back())
  {
   answer++;
   que[count] = 0;
   priority.pop_back();
   if (index == count)
    break;
  }
  count++;
 }
 return answer;
}
int main(void)
{
 int t;
 cin >> t;
 for (int i = 0; i < t; i++)
 {
  int n, index;
  cin >> n >> index;
  cout << solution(n, index) << "\n";
 }
 return 0;
}

---

문제 풀이

이번 문제에서는 간단히 프린터 큐를 구현하는 문제였다. 처음에는 class나 구조체를 활용하려고 하다 보니 많이 꼬이는 부분이 많았다. 그러나 인덱스를 활용하면 좀더 간단히 풀 수 있겠다는 생각이 들었다. 그래서 큐의 우선순위의 크기대로 sort시킨 배열을 하나 더 만들어서 우선순위를 확인하고, 아니게 되면 큐의 뒤에 추가시켜서 while을 돌리고, index의 위치를 정정시켜서 주어진 출력의 순서를 찾도록 했다.

문제 결과

문제 출처 https://www.acmicpc.net/problem/1966