[JAVA] BOJ(백준) - 프린터 큐 - 1966

문제 내용

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

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번째로 인쇄되게 된다.

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

 

---

문제 접근 방법

단순하게 접근해서 풀면되는 문제라고 생각한다.

입력받은 문서 중 중요도가 가장 높은걸 차례대로 뽑으면서 몇번뽑았는지 카운트 해준다.

그리고 문서를 뽑으면서 내가 뽑고자하는 문서일때 함수를 종료하면 끝인 문제다.

 

이 문제에서 중요한건

중요도가 같은 문서가 존재할 수 있기때문에 처음에 문서를 입력받을때 문서의 중요도와 더불어 순서도 기억해 놔야한다는 것이다.

따라서 문제를 풀기 위해 큐에 저장되는 요소는 문서의 중요도+순서를 기억할 수 있는 객체를 넣어 줘야한다. 이부분을 해결하기 위해 나는 중요도와 순서를 저장하는 객체를 생성해 큐에 저장시켜 줬다.

 

 

순서대로 풀이과정을 써보면

1. 큐에 객체저장.
   큐에 문서의 중요도와 순서를 저장할 수있는 객체를 만들어 저장시켜 준다.
   
   
2. 최댓값 찾기.
   큐에 저장된 값을 poll을 통해 처음부터 끝까지 최댓값을 찾으면서 add를 활용해 원래대로 되돌려 놓는다.
   
   
3. 카운트 하기.
   2번에서 찾은 최댓값을 큐에서 뽑고 카운트를 증가 시켜준다.
   이때 만약 뽑은 최댓값이 내가 원하는 문서라면 함수를 종료 시켜준다.

위의 과정을 내가 원하는 문서를 찾을때까지 반복해주면 풀리는 문제이다.

자세한 내용은 풀이를 보며 생각해보자.

 

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[] answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		answer = new int[T];
		
		for(int i=0; i<T; i++) {//테스트 케이스만큼 반복
			st = new StringTokenizer(br.readLine());
			Queue<printQ> Q = new LinkedList<printQ>();//테케마다 큐 새로 생성
			int N = Integer.parseInt(st.nextToken());//문서 개수
			int M = Integer.parseInt(st.nextToken());//원하는 문서의 순서 변수
			int impM = 0;//원하는 문서의 중요도 변수
			st = new StringTokenizer(br.readLine());
			
			//1번
			//큐에 문서 입력
			for(int j=0; j<N; j++) {
				int value = Integer.parseInt(st.nextToken());//중요도
				if(j==M) impM = value;//원하는 문서의 순서일때
				
				Q.add(new printQ(j,value));
			}
			
			//큐사이즈 1이면 문서한개임. 따라서 1번째로 뽑힘
			if(Q.size()==1) answer[i]=1;
			//printQueue(원하는문서 중요도, 원하는문서 순서, 문서저장된 큐)
			else answer[i]=printQueue(impM,M,Q); 
		}
		
		for(int a:answer) {
			System.out.println(a);
		}
	}
	
	//원하는 문서 몇번째로 뽑히는지 알아내는 메서드
	public static int printQueue(int impM, int M, Queue<printQ> Q) {
		int maxImp=Q.peek().imp;//중요도 최댓값을 큐의 첫번째값으로 초기화
		int maxSeq=0;//첫번째 문서이므로 0으로 순서 초기화
		int count=0;//몇번째로 뽑히는지 알려줄 변수
		int search=0;//큐 탐색횟수
		
		//2번
		//첫번째 while문 -> 큐전체 탐색하며 최댓값 찾기
		while(!Q.isEmpty()) {
			//반복문 돌다 큐사이즈 1이면 마지막이 원하는 문서라는 의미가됨.
			//따라서 지금까지 카운트한 count변수에 +1을 해주고 반환.
			if(Q.size()==1) return count+1;
			
			printQ pq = Q.poll();
			int crrSeq = pq.seq;//현재 순서
			int crrImp = pq.imp;//현재 중요도
			
			//현재 중요도가 지금까지 중요도가 최댓값인것 보다 크면
			//문서의 중요도 최댓값과 순서를 현재꺼로 갱신시켜줌.
			if(maxImp < crrImp) {
				maxImp = crrImp;
				maxSeq = crrSeq;
			}
			
			//큐 하나 요소 탐색했으면 다시 원래대로 삽입
			Q.add(new printQ(crrSeq, crrImp));
			//요소 하나 탐색할때 마다 search 증가.
			search++;

			//요소를 전부 탐색했을때
			if(search==Q.size()) {
				//maxImp가 0이라면 문서하나 뽑은뒤 나머지 문서가
				//모두 중요도가 같다는 의미가됨.
				//따라서 큐에 있는 첫번재 요소가 먼저 출력돼야 하기 때문에
				//문서의 최댓값 중요도와 순서를 큐의 가장 앞에 있는 원소로 할당
				if(maxImp==0) {
					maxImp=Q.peek().imp;
					maxSeq=Q.peek().seq;
				}
				
				//3번
				//두번째 while -> 위에서 찾은 최댓값에 해당하는 문서 출력
				//최댓값에 해당하는 문서가 출력될때까지 처음부터 끝까지 큐탐색하며
				//최댓값을 찾음.
				while(true) {
					printQ temp = Q.poll();
					int tempSeq = temp.seq;
					int tempImp = temp.imp;
					
					//지금 뽑은 요소가 최댓값과 순서가 같을때 최댓값 출력.
					//출력한다는 의미 -> 큐에서 요소를 없앤다.(바로 위에서 poll함)
					if(tempSeq==maxSeq && tempImp==maxImp) {
						count++;//출력할때 카운트 증가.
						//만약 내가원하는 문서이면 count 반환하고 종료.
						if(tempSeq==M && tempImp==impM) return count;
						break;//그게아니면 반복문 종료.
					}
					//만약 현재 뽑은 요소가 최댓값 문서가 아니면
					//다시 큐에 넣어줌.
					else {
						Q.add(new printQ(tempSeq, tempImp));
					}
				}
				
				//반복문 후에 변수 다시초기화
				maxImp=0;
				maxSeq=0;
				search=0;
			}
			
		}
		return count;
	}
}

//문서의 중요도와 순서를 저장해주는 클래스
class printQ{
	int seq;//순서
	int imp;//중요도
	
	//생성자
	public printQ(int seq, int imp) {
		this.seq = seq;
		this.imp = imp;
	}
}

 

---

마치며

큐를 계속 반복하면서 탐색 해주는 로직과 큐에 어떤 값을 저장시킬지 생각해낼 수 만 있다면 크게 어려운 문제는 아니라고 생각한다.