Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

19. 큐, 덱

큐와 덱을 구현하고 사용해 봅시다.

Java / Python

4. 프린터 큐

1966번

큐의 개념이 응용된 문제

이번 문제는 프린터로 문서를 출력한다고 하면 원래 FIFO에 따라 인쇄되는데, 그 인쇄 조건에 중요도를 적용하는 문제입니다. 현재 Queue에 있는 문서의 수와 중요도에 따라 어떤 한 문서가 몇 번째로 인쇄되는 지 찾는 것입니다. queue에서 M 번째 놓여있어 몇 번째로 인쇄되었는 지 궁금한 문서가 몇 번째로 인쇄되었는 지 출력합니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
import java.util.StringTokenizer;
import java.util.LinkedList;
 
public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());	
 
		while (T-- > 0) {
            
			LinkedList<int[]> queue = new LinkedList<>();	// Queue(연결 리스트)
            
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());			

			st = new StringTokenizer(br.readLine());
 
			for (int i = 0; i < N; i++) {
				// {초기 위치, 중요도}
				queue.offer(new int[] { i, Integer.parseInt(st.nextToken()) });
			}
 
			int count = 0;	// 출력 횟수
			
			while (!queue.isEmpty()) {	// 한 케이스 내 반복
				
				int[] front = queue.poll();	// 첫 번째 원소
				boolean isMax = true;	// front 원소가 가장 큰 원소인지 판단
				
				// front vs. queue 원소 중요도 비교 
				for(int i = 0; i < queue.size(); i++) {
					
					// 처음 뽑은 원소보다 큐에 있는 i번째 원소가 중요도가 클 경우 
					if(front[1] < queue.get(i)[1]) {						
						
						queue.offer(front);	// 뽑은 원소 및 i 이전의 원소들을 뒤로 
						for(int j = 0; j < i; j++) {
							queue.offer(queue.poll());
						}
						
						// front원소가 가장 큰 원소가 아니면 false, 탐색 끝
						isMax = false;
						break;
					}
				}
				
				// front 원소가 가장 큰 원소가 아니면 다음 반복문으로
				if(isMax == false) {
					continue;
				}
				
				// front 원소가 가장 큰 원소면 출력
				count++;
				if(front[0] == M) {	// 찾고자 하는 문서면 이 테스트케이스 종료
					break;
				}
 
			} 
			sb.append(count).append('\n'); 
		}
		System.out.println(sb);
	}
}

• Python

test_case = int(input())

for _ in range(test_case):
    N, M = map(int,input().split())

    print_list = list(map(int,input().split()))
    check_list = [0 for _ in range(N)] 
    check_list[M] = 1 # 궁금한 문서위치 저장

    cnt=0
    while True:
        if print_list[0] == max(print_list):
            cnt+=1

            if check_list[0] != 1:
                del print_list[0]
                del check_list[0]
            else:
                print(cnt)
                break
        else:
            print_list.append(print_list[0])
            check_list.append(check_list[0])
            del print_list[0]
            del check_list[0]