[알고리즘] 프린터 큐 (백준, 1966)

문제

1966번: 프린터 큐

 

풀이

GitHub - ruhz3/coding-test: To prepare for coding test

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

public class Main {
	public static int print(LinkedList<Integer> queue, int[] priority) {
		int first;
		boolean canPrint;
		while(true) {
			// 00. canPrint가 중간에 false로 바뀌지 않는다면 출력될 것이다. 
			canPrint = true;
			
			// 01. 대기열의 첫 번째 원소 뒤에 우선순위가 높은 것이 있다면, 맨 뒤로 보내고 canPrint를 false로 변경한다.  
			first = queue.peek();
			for(int i = 1, len = queue.size(); i < len; i++) {
				if(priority[queue.get(i)] > priority[first]) {
					queue.add(queue.poll());
					canPrint = false;
					break;
				}
			}
			
			// 02. 뒤에 우선순위가 더 큰 것이 없어지면, 이 조건문을 통과할 것이다. 
			if(canPrint)
				break;
		}
		
		return queue.poll();
	}
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		int N, M;
		LinkedList<Integer> queue = new LinkedList<>();
		int[] priority;
		int count;
		while(T > 0) {
			// 00. N, M을 입력 받는다.
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			// 01. 현재 큐 상태를 입력 받는다.
			queue.clear();
			priority = new int[N];
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i < N; i++) {
				priority[i] = Integer.parseInt(st.nextToken()); 
				queue.add(i);
			}
			
			// 02. 출력을 진행하고, 원하는 문서 번호가 나오면 몇 번만에 나왔는지 출력한다.
			count = 1;
			while(true) {
				if(print(queue, priority) == M) {
					System.out.println(count);
					break;
				} else {
					count++;
				}
			}
			T--;
		}
	}
}

문제가 주는 대로 그대로 구현했다. 프린터 '큐'라는 말에 아무 생각없이 Collection의 Queue로 구현을 시도 했다. 하지만 작성하다 막히고 나서야, Queue는 중간의 원소들을 순회할 수가 없다는 사실이 기억났다! 따라서 중간의 원소들을 순회할 수 있는 연결 리스트로 코드를 수정했다. 실제 코딩 테스트에서 헤매지 않으려면, Collection들의 상속관계와 각 메소드를 알고 있는 것이 좋을 것 같다.

 

Collection의 상속관계를 한 번 정리해야 할 것 같다.