[백준 BOJ][queue] 1966 프린터 큐

링크

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

풀이

 

입력은 위와 같이 첫 줄에는 문서의 개수와 위치를, 두 번째 줄에는 큐에 들어갈  문서의 중요도가 차례대로 주어집니다.

 

중요한 규칙은 중요도가 높은 문서를 먼저 인쇄한다는 점입니다. 지금 큐에 가장 앞에 있는 문서가 가장 높은 중요도가 아니라면 뒤로 보내고 아니면 출력합니다.

 

두 가지 방법을 생각해볼 수 있습니다.

1. 큐로 구현하기

2. 배열로 순회의 시작점을 달리하여 큐처럼 동작하게 하기

 

큐로 구현한다면 프린터 큐에는 (중요도, index)가 한 쌍으로 저장돼야 합니다. 그리고 priority queue를 이용하여 현재 큐에 남아있는 중요도 중에 가장 큰 게 어떤 건지 확인해 비교하면서 출력할 건지, 뒤로 넘길지, 정답에 도달했는지 체크합니다.

 

 

첫 번째 방법이 큐에서 문서가 실제로 뒤로 이동하는 식이었다면, 두 번째 방법은 화살표 하나가 배열을 돌면서 출력하는 방법입니다. 우선 중요도를 9부터 1까지 내리면서 출력을 수행하게 됩니다. 마지막으로 출력된 문서가 몇 번째 index인지 기억하고 한 단계 낮은 중요도에서 체크할 때 이를 시작점으로 두고 순회합니다. 마지막으로 출력된 문서가 k번째라면 k -> n을 순회하고 0 -> k-1까지 순회합니다. 출력된 문서가 있다면 index를 기억하고 이를 반복합니다.

 

예를 들어, 1 1 9 1 8 1 1이라는 예제에서 9가 출력된다면 k=2가 될 것이고, 뒤에 있는 1 8 1 1 다음 앞의 1 1을 체크하는 것이죠. 이때 8이 출력됐기 때문에 k=4가 됩니다.

 

 

 

첫 번째 방법은 아무 때나 새로운 문서가 큐에 들어와도 잘 작동하지만, 두 번째는 쓸데없는 반복이 많고, 고정된 자료에서만 수행하는 코드라는 점에서 자료구조를 사용하는 게 더 좋은 것 같습니다.

 

코드

// 1966_프린터 큐_1번 코드
#include <cstdio>
#include <queue>
using namespace std;

int T;

int main() {
  scanf("%d", &T);

  while (T--) {
    int n, idx, priority, cnt = 1;
    queue<pair<int, int>> q;
    priority_queue<int> pq;

    scanf("%d %d", &n, &idx);

    for (int i = 0; i < n; i++) {
      scanf("%d", &priority);
      q.push({priority, i}); // 중요도, idx 순서대로 입력
      pq.push(priority); // 중요도만 저장하여 내림차순으로 정렬
    }

    while (!q.empty()) { // 원하는 거 뽑을 때까지 프린트 시작

      if (q.front().first == pq.top()) { // 지금 뽑아야할 중요도인가?
        if (q.front().second == idx) {   // '궁금한 문서'인가?
          printf("%d\n", cnt); // 맞으면 몇 번째로 출력되는지 출력 후 종료
          break;
        }
        cnt++;
        q.pop();  // 큐에서도 pop
        pq.pop(); // 중요도에서도 pop

      } else { // 지금 뽑을 문서가 아닌 경우
        q.push({q.front().first,
                q.front().second}); // 중요도가 낮으면 맨 뒤로 보냄
        q.pop();                    // 앞에 있던 거 pop 처리
      }
    }
  }

  return 0;
}

 

//1966_프린터 큐_2번 코드
#include <cstdio>
using namespace std;

int T, n;

int main() {
  scanf("%d", &T);

  while (T--) {
    int arr[101] = {}; // 중요도
    int count = 1, idx;
    scanf("%d %d", &n, &idx);

    for (int i = 0; i < n; i++) {
      scanf("%d", &arr[i]);
    }

    int tmp = 0;	// 마지막으로 출력된 문서의 위치
					// 이게 있어야 그 뒤로부터 출력이 되기 때문에 알아야 된다

    int flag = 0;	// idx가 출력됐는지


    for (int i = 9; i >= arr[idx]; i--) {	// 중요도 9->idx의 중요도까지 돌면서 
      int start = tmp;
      for (int j = start; j < n; j++) {	// 전 중요도에서 마지막으로 출력된 문서부터 그 전 index까지 순회 / 가장 높은 중요도면 0부터 순회
        if (arr[j] == i) {	// 출력 가능하면 출력
          if (j == idx) {	// idx가 출력되면 flag 1로 바꾸고 break
            flag = 1;
            break;
          }
          count++;
          tmp = j;	// 마지막으로 출력된 문서 위치 저장
        }
      }
			
      if (flag) break;	// idx가 전 tmp보다 뒤에 있었을 경우

      for (int j = 0; j < start; j++) {		
        if (arr[j] == i) {	// 출력 가능하면 출력
          if (j == idx) break;	// idx가 출력되면 break (다 돌았다는 뜻)
          count++;
          tmp = j;	// 마지막으로 출력된 문서 위치 저장
        }
      }
    }

    printf("%d\n", count);
  }

  return 0;
}