[JAVA] 백준 1966번: 프린터 큐

<문제> 

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

1966번: 프린터 큐

 

처음에 문제를 어떻게 접근해야 할 지 고민이 많았다.

배열로 접근하자니 너무 복잡해질 것 같았고,  큐를 사용하고자 하니 (순서, 중요도) 라는 2개의 값을

어떻게 넣어야할지 몰라 막막했다. 큐에 대한 이해가 많이 부족해서 이 문제가

나에게 어려웠던 것 같다. 여러 블로그를 찾아보다가, 내 기준에서 가장 이해가 잘 됐던

블로그를 운 좋게 찾아서 문제를 해결할 수 있었다. 

감사합니다 정말로,, 🫶🏻

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
//프린터 큐
class Printer {
	int sequence; //순서
	int importance; //중요도
	
	Printer(int sequence, int importance){
		this.sequence=sequence;
		this.importance=importance;
	}
	
}
public class P1966 {
	//몇 번째로 출력되는지 계산하는 함수 
	static int solution(Queue<Printer> q, PriorityQueue<Integer> pq, int m) {
		int count=1;
		
		while(true) {
			while(pq.peek()!=q.peek().importance) {
				q.offer(q.poll());
			}
			if(q.peek().sequence==m) {
				break;
			}
			q.poll();
			pq.poll();
			count++;
		}
		return count;
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int test_case=Integer.parseInt(br.readLine());
		
		for(int i=0;i<test_case;i++) {
			st=new StringTokenizer(br.readLine());
			int n=Integer.parseInt(st.nextToken()); //문서의 개수
			int m=Integer.parseInt(st.nextToken()); //궁금한 문서가 현재 몇 번째에 놓여있는지
			
			Queue<Printer> q=new LinkedList<>(); // 큐 생성
			//우선순위큐 내림차순 정렬
			PriorityQueue<Integer> pq= new PriorityQueue<>(Comparator.reverseOrder());
			
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) { //문서의 중요도 
				int importance=Integer.parseInt(st.nextToken());
				q.offer(new Printer(j,importance)); //큐에는 Printer 객체(순서, 중요도) 를 저장
				pq.offer(importance); //우선순위큐에는 중요도만 저장 
			}
			
			System.out.println(solution(q,pq,m));
		}
	}

}

 

✏️풀이 방법

 

큐와 우선순위 큐를 사용하여 문제를 해결했다.

- 큐: Printer 클래스를 정의하여 Printer(순서, 중요도) 객체를 큐에 넣음

- 우선순위큐: 중요도만 우선순위 큐에 저장 (내림차순) 

                                                                 

ex ) n= 6, m=0

중요도: 1 1 9 1 1 1 일 때 

큐의 상태

우선순위 큐의 상태 (내림차순)

 

1. 우선순위 큐의 맨 앞에 있는 수와 큐의 중요도를 비교

 

2. 같지 않으면, 그 값을 큐에서 빼서 다시 큐에 넣음 

=> 우선순위 큐의 맨 앞 숫자 == 첫번째 큐의 중요도가 될 때까지 이 과정을 반복

큐가 우선순위 큐의 중요도대로 정렬된 상태

 

3. 이렇게 중요도대로 큐가 제대로 정렬이 되고 난 후에,

큐와 우선순위큐에서 값을 빼면서 count 를 증가시킨다. 

 

4. 몇 번째로 출력되는지 궁금한 문서의 번호(m)과 큐에 들어있는

Print 객체의 sequence 값이 같아지면  반복문을 종료하고 count를 출력한다.

 

 

✏️  느낀점

 

실버 3 문제인데, 큐와 우선순위큐 사용법을 잘 알지 못해서 어려웠다.

이번 기회를 통해 큐에 대해 좀 더 알게 된 것 같다.

다음에 비슷한 문제가 나오면 쉽게 풀 수 있도록 완전 내 것으로 만들어야겠다.

 

 

 

 

 

 

참고 블로그

---

https://dkyou.tistory.com/316