[BOJ] 백준 1966 프린터큐

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

Approach

문제에서 설명한 중요도를 반영해서

완전탐색 기반으로 단순 선형 Queue만으로도 구현할 수 있다.

중요도가 반영되는 특징은 "우선순위 큐"를 사용하면 보다 쉽게 처리할 수 있다.

▶ [큐] Queue란?  

▶ 우선순위 큐 (Priority Queue) 

▶ [STL] Priority_queue 

 

- 실제 프린터 대기열: queue

- 우선순위가 반영된 대기열: priority queue

두 개의 큐를 비교하며 실제처리해야할 것이 맞는지 확인해서

출력 혹은 보류 처리한다.

---

#include <iostream>
#include <queue>
using namespace std;
int ans, TC;
int N, M, priority;
queue<pair<int, int>> que;
priority_queue<int> pq;

int printer()
{
    while (!que.empty())
    {
        int idx = que.front().first;
        int val = que.front().second;
        // 프린터 대기열 큐에 있는 원소를 꺼낸다.
        que.pop();
        // 우선순위가 반영된 순서와 일치하는지 확인
        if (pq.top() == val)
        {
            // 일치한다면 그대로 출력
            pq.pop();
            ++ans;
            // 찾고자 하는 대상인 경우 return
            if (idx == M)
            {
                return ans;
            }
        }
        else // 우선순위에 맞지 않으면 순서를 뒤로 보낸다.
        {
            que.push({ idx,val });
        }
    }
}

void init()
{
    ans = 0;
    while (!que.empty()) { que.pop(); }
    while (!pq.empty()) { pq.pop(); }
}

void input()
{
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
    {
        cin >> priority;
        que.push({ i, priority });
        pq.push(priority);
    }
}

int main()
{    
    // freopen("input.txt", "r", stdin);
    cin >> TC;
    for (int tc = 0; tc < TC; ++tc)
    {
        init();
        input();
        cout << printer() << endl;
    }
}

 

Java

import java.util.Scanner;
class Queue {
   int front, rear;
   int[] queue;
   
   public Queue(int size) {
      front = 0;
      rear = 0;
      queue = new int[size];
   }

   public void push(int value) {
      queue[rear++] = value;
   }

   public void pop() {
      front++;
      return;
   }
      
   public int find_print_order(int target_idx){
      int count = 0;
      while(true){
         int check = 0; // 타겟 인덱스 차례인지 확인
         int flag = 0; // 위치변화 여부  
         if(front == target_idx){
            check = 1;
         }
         for(int i=front+1; i<rear; i++){
            if(queue[front] < queue[i]){
               flag = 1;
               break;
            }
         }
         if(flag == 0 && check == 1){ // 타겟 인덱스의 우선순위가 가장 높고 출력할 차례이면 종료
            count++;
            break;
         }
         if(flag == 1){ // 우선순위가 높은것이 존재
            push(queue[front]); // 제일 앞의 것을 뒤로 보낸다.
            if( check == 1 ){ // front가 타겟인데 뒤로 밀려난 것이라면
               target_idx = rear-1; // 마지막 인덱스를 새로운 타겟 인덱스로 설정
            }
         }
         if(flag == 0 && check == 0){ // 모든 우선순위가 동일한 것들만 남았을 때 or 내림차순 같은 꼴로 되었을  
            int opt = 0;
             for(int k=front; k<rear-1; k++){
                if(queue[k] != queue[k+1]){ // 모두의 우선순위가 동일한지 내림차순 꼴인지 확인한다.  
                    opt = 1;
                    break;
                }
            }
            if(opt == 0){ // 모든 우선순위가 동일한 경우라면
               count = count + (target_idx - front + 1);
               break;
            }
            else{
               count++;
            }
         }
         front++;
      }
      return count;
   }
   
   public void print_queue(){
      for(int i=front; i<rear; i++){
         System.out.print(queue[i] +" ");            
      }
      System.out.println();
   }
}

public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int T = sc.nextInt();
      Queue result_Q = new Queue(T);
      for(int i=0; i<T ;i++){
         // 각 테스트케이스 만큼의 배열 크기 지정
         int n = sc.nextInt();
         
         // 타겟 인덱스 입력 받기
         int target_idx = sc.nextInt();
         
         // 지정된 크기 만큼의 원소들(우선순위_중요도) 큐에 삽입
         Queue item_Q = new Queue(10000); // 규칙 구현을 위해 여 크기를 확보
         for(int j=0; j<n; j++){
            int value = sc.nextInt();
            item_Q.push(value);
         }
         
         // 규칙을 만족하는 큐의 규칙 구현
         int result = item_Q.find_print_order(target_idx);         
         
         // 타겟 인덱스의 출력순서를 result_Q에 삽입
         result_Q.push(result);
      }
      result_Q.print_queue();
   }
}