[백준/java] 1966번: 프린터 큐

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

1966번: 프린터 큐

1966번: 프린터 큐

 

문제가 어떤 문제인지는 알겠으나 막상 풀려고하니 생각보다 시간이 많이 지났던 문제이다.

큐의 사용 방법 + 구현력을 요구하는 문제같았다.

 

반응형

※ 문제 해결 방법

(1) Paper 클래스 선언

   : 먼저 Paper 클래스를 선언하여 클래스 필드에 우선순위와 해당 순서가 맞는가에 대한 변수를 선언했다.

(2) 큐 생성 및 우선순위 내림차순 정렬

   : Paper클래스를 넣는 큐를 생하고 우선순위를 받은 배열을 내림차순으로 정렬한다. << 역순 배열은 최대값을 비교시 사용할 것이다

(3) 배열의 반복 인덱스가 배열 길이만큼 될때까지 순회한다.

   : 먼저 우선순위가 같은지 체크한다.

   : 같으면 해당 순서가 뽑으려고 하는 순서가 맞는지 확인하고 맞으면 반복문을 나간다.

   : 순서가 맞지 않으면 그냥 출력하고 배열 반복 인덱스를 증가시킨다.

   : 우선순위가 맞지 않으면 뽑아서 뒤로 다시 보낸다.

 

package queue;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class PrinterQueue {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int loc = Integer.parseInt(st.nextToken());
			String[] strArr = br.readLine().split(" ");
			Integer[] arr = new Integer[N];
			
			// 큐에 우선순위들을 넣는다.
			Queue<Paper> q = new LinkedList<Paper>();
			for (int i = 0; i < strArr.length; i++) {
				int priority = Integer.parseInt(strArr[i]);
				boolean isRight = loc == i;		// loc의 위치가 맞는가 안맞는가
				arr[i] = priority;				// 우선순위
				q.add(new Paper(priority, isRight));
			}
			
			// 큐에 들어가는 우선순위를 내림차순으로 정렬
			Arrays.sort(arr, Collections.reverseOrder()); 
			
			int cnt = 0;
			int k = 0;
			
			while(k < arr.length) {
				int max = arr[k];
				Paper p = q.peek();
				
				if(p.priority == max) {
					cnt++;
					if(p.isRight) break;
					q.poll();
					k++;
				} else {
					q.add(q.poll());
				}
			}
			
			bw.write(cnt + "\n");
		}
		
		bw.flush();
	}
}

class Paper {
	int priority;
	boolean isRight;
	
	public Paper() {}
	public Paper(int priority, boolean isRight) {
		this.priority = priority;
		this.isRight = isRight;
	}
}