[BOJ 실버3 JAVA] 1966 프린터 큐

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

1966번: 프린터 큐

 

 

1. 첫 인상

 - Queue의 특징인 선입 선출을 활용한 것인데, 이를 응용하여 우선순위라는 개념도 더해져 처음에는 손코딩으로 테스트 케이스의 정답을 찾는 것 시간도 오래걸렸음

 - 단순한 Queue 문제이지만, 오늘 처음 Queue에 대한 개념을 알게 된 나로써는 중간 중간 print를 찍어 확인하며 문제풀이를 진행했음

2. 생각하기

 - 우선 우선순위와 인덱스를 함께 고려해야 하므로, 이 둘을 한꺼번에 담아두고 비교할 것이 필요했는데, 사실 Queue를 생성할 때 Queue<Integer>만 사용해봤지(오늘 처음 배운 내용이라) Queue<int[]> 형식의 원소 형태도 입력이 가능할까 했는데 가능했다.

 - 그래서 먼저 우선순위의 최대 값을 찾는 것이 우선이라고 생각했고,

 - 또 반복문으로 우선순위에 해당하는 것이 나오면 poll()하고, 아니면 poll()한 것을 다시 offer() 해야겠다고 생각.

 - 그리고 우리가 출력해야 할 특정 위치의 문서가 출력되는 순서를 구하려면 cnt가 필요하여 생성 후, poll()할 때마다 cnt++ 진행

 - 마지막으로, 조건문으로 우선순위도 max이고, 우리가 찾는 위치도 일치한다면, 바로 cnt++한 뒤 반복문을 종료한 뒤 출력하면 될 것으로 생각했는데

 - 그런데 초반에 위 조건이 반복문의 아래쪽에 있어서 초반에 걸러지지 않아서 무한 루프가 걸린 적도 있어서 다시 정신차리고 위치조정 후 채점하니 성공!

3. 코드

package codingtest.boj;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_220221_1966_Silver3_프린터큐 {
	public static void main(String[] args) {
		/*
		 * T : 테케
		 * N, M : 문서의 개수, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 큐에서 몇 번째에 놓여있는지.
		 * N개의 문서의 중요도가 차례대로
		 * 
		 */
		
		/*
		 * 1. 우선순위 max 찾기
		 * 2. peek()해서 우선순위 max 값이 일치하고, 원하는 출력 순서를 갖는 문서가 같으면 cnt++하고 break
		 * 3. 위 조건이 안걸렸을 시, max값이 나오면 poll, 아니면 다시 poll한 뒤 offer로 뒤에 넣어주기
		 * 4. 1~4 반복
		 * 
		 */
		
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int tc=0; tc<T; tc++) {
			Queue<int[]> qu = new LinkedList<>();
			int[] pri; // 문서 번호와 우선순위 받을 배열
			
			int N = sc.nextInt();
			int M = sc.nextInt();
			
			for(int i=0; i<N; i++) {
				qu.offer(new int[] {i, sc.nextInt()});
			}
			// ---- 입력 : Queue를 길이가 2인 int 배열로 받음 배열은 {문서의 순서, 우선순위}로 받음
			
			int cnt = 0;
			outer : while(!qu.isEmpty()) {
				// ---- 큐가 빈 큐가 될 때까지 반복
				// ---- 우선순위 최대값 찾기
				int max = -1; // 초기 max 값은 -1
				for(int i=0; i<qu.size(); i++) {
					int temp = qu.peek()[1];
					if(temp > max) {
						max = temp;
					}
					qu.offer(qu.poll());
				}

				// ---- 우선순위가  위에서 찾은 max 값과 일치하고, 우리가 찾고 싶은 순서의 문서가 같다면 cnt++ 후 break
				if(qu.peek()[0] == M && qu.peek()[1] == max) {
					qu.poll();
					cnt++;
					break outer;
				}
				
				// ---- 위 조건에서 걸린 걸리지 않으면, 우선순위가 max이면 poll().
				if(qu.peek()[1] == max) {
					qu.poll();
					cnt++;
				// ---- 우선순위 max가 아니면 poll한 뒤 offer 하여 뒤에 다시 넣어주기
				}else {
					qu.offer(qu.poll());
				}
			}
			// ---- 위 순서 반복
			
			System.out.println(cnt);
		}
	}
}

4. 느낀 점

 - 오늘 처음 Queue에 대한 내용을 배웠고, 이것 저것 Queue API를 활용하며 실험해 볼 수 있어서 좋은 문제였다고 생각한다.

 - 오늘 강사님께서 Queue는 혼자 쓰이는 것보다는 너비우선, 깊이우선 같은 알고리즘 기법과 같이 사용된다던데, 그러려면 빨리 머리 속에서 Queue에 대한 내용이 그려져야하고, 그러려면 기초가 탄탄해야된다고 생각하는데, 오늘 이것 저것 구글링을 해보며 부딪친 것이 많은 도움이 될 것 같다.

 

- 추가로, 매일 5문제정도는 풀이하는 것 같은데 블로그 포스팅은 그만큼 성실하지 못한데, 반성하고 매일 포스팅 꼭 해야겠다