[백준] 1966번: 프린터 큐(구현, 큐)

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

1966번: 프린터 큐

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(bf.readLine());
		for(int t=0; t<tc; t++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int N = Integer.parseInt(st.nextToken());	// 문서의 수
			int x = Integer.parseInt(st.nextToken());	// 몇번째로 인쇄되었는지 궁금한 문서
			int ans = 0;
			st = new StringTokenizer(bf.readLine());	// 문서의 중요도
			LinkedList<Integer> q = new LinkedList<Integer>();
			for(int i=0; i<N; i++) 
				q.add(Integer.parseInt(st.nextToken()));	// 큐에 문서의 중요도 추가
			
			while(!q.isEmpty()) {
				boolean flag = true;	// 현재 문서보다 중요도가 높은 문서가 있는지 체크
				for(int i=1; i<q.size(); i++) {
					if(q.peek() < q.get(i)) {	// 현재 문서보다 중요도가 높을경우
						flag = false;
						break;
					}
				}
				
				// 문서내 현재 문서보다 중요도가 높은게 없는경우
				if(flag) {
					ans ++;		// 현재 목록 인쇄 +1
					q.poll();	// 현재 목록 인쇄해서 제거하기
					if(x == 0) 	break;	// 현재 인쇄하려는 문서가 궁금한 문서인경우
					else 	x --;		// 현재 인쇄하려는 문서가 궁금한 문서가 아닌경우
					
				}
				
				// 문서내 현재 문서보다 중요도가 높은게 있는경우 -> 현재 문서 가장 뒤로 이동
				else {
					// 현재 목록 제거 후 마지막에 넣기
					int temp = q.poll();
					q.add(temp);
					
					/*
					 * 현재 문서가 궁금한 문서인경우 -> 가장 뒤로 이동하므로 Queue의 사이즈-1로 인덱스 지정
					 * 궁금하지 않은 문서인경우 -> 인덱스 -1
					 */
					if(x == 0)	x = q.size()-1;
					else		x -= 1;
					
				}
			}
			System.out.println(ans);
		}
		bf.close();
	}

}

풀이

중요도가 동일한 문서들의경우, 처리를 어떻게 해야될지 모르겠어서 타 블로그를 참고했다.

https://qlyh8.tistory.com/153

 

 

조건은 다음과 같다.

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

 

해결법은 다음과 같다.

• 현재 문서도의 중요도를 확인하고, 현재 문서보다 중요도가 높은게 있는지 체크한다.
• 만약 현재 문서보다 중요도가 높은게 없는경우(flag = true) - <현재 문서의 중요도가 가장 높은경우>
•  - 현재 목록을 인쇄하서 카운트를 증가시키고, 현재 인쇄를 제거한다.
•  - 만약 현재 문서가 내가 궁금해하는 인쇄의경우 while문을 탈출하고,
•  - 만약 현재 문서가 궁금해하지 않는 인쇄의경우 - 인덱스를 1씩 감소한다.(x--)
• 만약 현재 문서보다 중요도가 높은게 있는경우(flag = false) - <현재 문서의 숫자가 가장 높지 않는경우>
•  - 만약 현재 문서가 궁금해하는 문서인경우 -> 큐의 마지막에 넣기 때문에 인덱스를 size-1로 설정한다.
•     -- (배열과 동일하게 인덱스는 0부터 시작하므로, size-1로 설정한다.)
•  - 만약 현재 문서가 궁금하지 않은 문서인경우 -> 인덱스를 1씩 감소한다.(x--)
•  - 그 후 현재 문서를 제거(poll()) 후 마지막에 삽입(add())한다.

 현재 목록을 인쇄해서 카운트를 증가시키고, 현재 인쇄를 제거한다.