Taxol

I’ve always been.

백준 1966 - 프린터 큐

Updated:

Java

1966 번 - 프린터 큐

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

  1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
  2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

문제 출처

접근 방법

제일 앞의 문서의 중요도와 나머지 중요도를 비교하여 작으면 뒤로 보내고 크면 출력을 한다. 출력을 할 때마다 순서를 부여하고, 입력에서 주어진 문서가 출력 되었을 때 순서를 출력한다.

구현

각 문서의 초기 순서와 중요도를 Pair를 통해 구현하였다.
문서가 queue에서 다 poll 될때까지 반복하며

  1. queue의 제일 앞의 문서를 뽑는다.
  2. 나머지 queue의 문서를 하나씩 poll하여 중요도를 비교하고 다시 offer를 반복하여 순환한다.
  3. 1번의 문서의 중요도가 제일 크면 순서를 부여하고, 아니면 offer하여 제일 뒤로 보낸다.
  4. 주어진 초기 순서의 문서가 출력 될 때까지 반복한다.

코드

/*
1966번 - 프린터 큐
https://www.acmicpc.net/problem/1966
*/

import java.util.*;
import java.io.*;

public class Main {
	
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk; 
    	
    	int tc = stoi(br.readLine());
    	Queue<Pair> dc = new LinkedList<Pair>();
    	int n, m, cnt = 1;
    	while(tc-- != 0) {
    		// 초기화  시작
    		dc.clear();
    		cnt = 1;
    		stk = new StringTokenizer(br.readLine());
    		n = stoi(stk.nextToken());
    		m = stoi(stk.nextToken());
    		stk = new StringTokenizer(br.readLine());
    		for(int i = 0; i < n; i++)
    			dc.offer(new Pair(stoi(stk.nextToken()), i));
    		// 초기화 끝
    		
    		boolean isBiggest = true;	
    		Pair curP, nextP;
    		while(!dc.isEmpty()) {
    			isBiggest = true;
    			curP = dc.poll();						// 제일 앞의 문서를 뽑는다.
        		for(int i = 0; i < dc.size(); i++) {	// 나머지 문서들을 순환하여 중요도를 비교한다.
	    			nextP = dc.poll();
	    			if(curP.first < nextP.first)
	    				isBiggest = false;
	    			dc.offer(nextP);
	    		}
        		if(isBiggest) {							// 제일 중요도가 크고
        			if(curP.second == m) {				// 문제에서 주어진 문서이면
        				System.out.println(cnt);		// 출력하고 종료
        				break;
        			}
        			cnt++;								// 출력 순서를 올린다.
        		}
        		else {
        			dc.offer(curP);
        		}	
    		}
    	}
    	
    	br.close();
    }
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
    
    static class Pair {
    	int first;
    	int second;
    	Pair(int a, int b){
    		this.first = a;
    		this.second = b;
    	}
    }
}

총평

난이도

⭐⭐★★★

후기

프로그래머스에서 풀었던 문제를 복습하였다.

개선할 점

없

You may also enjoy