본문 바로가기
알고리즘/백준

1966번 문제 : 프린터 큐

by son_i 2023. 3. 24.
728x90

1966번: 프린터 큐 (acmicpc.net)

 

1966번: 프린터 큐

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에

www.acmicpc.net

 

자바에 큐라는 자료구조가 있나 ? 있네 

Queue <Integer> queue = new LinkedList<>(); //인터페이스이기 때문에 큐 인터페이스를 상속받아 구현한 LinkedList클래스를 사용

근데 이건 큐보다는 해시맵을 이용해서 

각 문서의 갯수(정수값key)에 중요도를 value로 해서 넣어주면 될 듯. 중요도는 중복이 된다고 했으니 가능

 

그런데 HashMap 자체가 입력순서를 유지하는 컬렉션이 아니래 ,.,,,,,,,,,,,,,,ㅠ

그냥 ArrayList로 하는 것도 괜찮을 것 같다. -> 음 제일 앞에 있는 list.get(0) 이 중요도가 높고 그 값이 내가 원한 index값의 중요도랑 같은 값이라면,, 으로 했는데 중요도는 중복이 가능하니까 그걸 구분할수가 없다.

 

결국은 자료구조 Queue를 사용해야한다고 한다. 그런데 일반적인 큐가 아닌

Priority Queue

를 써야한다. PriorityQueue란 우선순위 큐로써 일반적인 큐의 FIFO구조를 가지면서 데이터 들어온 순서대로가 아니라 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나감. 완전 문제에 적합하자나 !

 

흠 근데 이걸로 안 하고 Queue로 해봤다.

정말 이해하기가 어려웠다.

내일 다시 공부해야할 듯

package algorithm;

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

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int num = Integer.parseInt(br.readLine());
	
		
		while( num-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int count = Integer.parseInt(st.nextToken()); //문서의 갯수
			int index = Integer.parseInt(st.nextToken()); //몇 번째로 인쇄되었는지 궁금한 문서가 큐에서 몇 번째에 있는지 나타내는 정수
	
			LinkedList <int[]> q = new LinkedList<>();
			
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<count;i++) { //문서의 갯수만큼 큐에 인덱스와 중요도를 배열로 함께 넣음
				q.offer(new int[]{i,Integer.parseInt(st.nextToken())});
			}
			
			int check = 0;
			while(!q.isEmpty()) { //한 케이스에 대한 반복문
				int []first = q.poll(); //제일 앞에있는 값을 뽑아서 first 배열에 인덱스, 중요도 순으로 넣음.
				boolean isMax = true;
				for(int i=0;i<q.size();i++) {
					if(first[1] < q.get(i)[1]) {
						
						q.offer(first);
						for(int j=0;j<i ;j++) {
							q.offer(q.poll());
						}
						isMax = false; // 가장 처음 뽑은 front원소가 가장 큰 중요도를 가지지 않았음.
						break;
					}
				} 
				if( isMax == false) {
					continue;
				}
				check++;
				if(first[0] ==index) 
					break;
			}
			sb.append(check).append("\n");
			}
		System.out.println(sb);	
	}	
}

다른 블로그 참고해서 겨우겨우 완성....

다시 이해하고 다시 풀어보자

 

package algorithm;

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

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int num = Integer.parseInt(br.readLine());
	
		while(num-- >0) { //num만큼 테스트 케이스 반복
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); //문서의 갯수
			int M = Integer.parseInt(st.nextToken()); //찾고싶은 인덱스
			
			LinkedList <int[]> q = new LinkedList<>();
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<N;i++) {
				q.offer(new int[] {i, Integer.parseInt(st.nextToken())} ); //큐 세팅
			}
			int count = 0;
			while(!q.isEmpty()) {
				int poll[] = q.poll();
				boolean isMax = true;
				
				for(int i=0;i<q.size();i++) {
					if(poll[1]<q.get(i)[1]) { //중요도가 더 큰게 있다면
						q.offer(poll); //뽑았던 맨 처음 값을 맨 뒤에 추가
						isMax = false;
						
						for(int j=0;j<i;j++) { //중요도 큰 요소보다 앞에있는 값들을 poll해서 맨 뒤에 붙여줌
							q.offer(q.poll());
						}
						break; //여기에 break안 걸면 최댓값 찾아도 모든 큐를 탐색해서 메모리 초과가 나옴.
					}
				}				
				if(isMax == false)
					continue;
				
				count++;
				if(poll[0] == M)
					break;
			}
			sb.append(count+"\n");
		}
		System.out.println(sb);
	}	
}

내가 최대한 풀어봄 근데 이해가 아니라 암기해서 푼 거 같은 느김이다 ㅠ

 

큐 공부 참고 사이트

자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기 (tistory.com)

 

자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기

자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly LinkedList) 4. 이중

st-lab.tistory.com

자바 [JAVA] - 연결리스트를 이용한 Queue (큐) 구현하기 (tistory.com)

 

자바 [JAVA] - 연결리스트를 이용한 Queue (큐) 구현하기

자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly LinkedList) 4. 이중

st-lab.tistory.com

[백준] 1966번 : 프린터 큐 - JAVA [자바] (tistory.com)

 

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

www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러

st-lab.tistory.com

[알고리즘 PS] 백준 1966 프린터 큐 자바 문제 풀이 (tistory.com)

 

[알고리즘 PS] 백준 1966 프린터 큐 자바 문제 풀이

문제 해당 포스팅은 백준의 1966번 프린터 큐 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 문제 예제 입력 & 출력 해결법 주의 해야할

wonit.tistory.com

백준1966 프린터 큐 자바 : 네이버 블로그 (naver.com)

 

백준1966 프린터 큐 자바

의외로 어려웠던 문제였다... 문제를 속독했을 때는 PriorityQueue로 했는데 그렇게 간단한게 아닌걸... ...

blog.naver.com

[Deque]문제#2. 프린터 큐(백준 196.. : 네이버블로그 (naver.com)

 

[Deque]문제#2. 프린터 큐(백준 1966번),자바

1966번: 프린터 큐 (acmicpc.net) 이문제는 데큐를 활용하였는데, 푸는 과정에서 실수한 부분들이 많았다 &...

blog.naver.com

참고해서 큐의 개념을 완벽하게 익히자 !

728x90

'알고리즘 > 백준' 카테고리의 다른 글

2164번 문제 : 카드 2  (0) 2023.03.29
2108번 문제 : 통계학  (0) 2023.03.29
1929번 문제 : 소수구하기  (0) 2023.03.22
1920번 문제 : 수 찾기  (0) 2023.03.20
1874번 문제 : 스택 수열  (0) 2023.03.19