1966번 문제 : 프린터 큐

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

1966번: 프린터 큐

 

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

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 (덱) 구현하기

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

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

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

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

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

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

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

백준1966 프린터 큐 자바

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

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

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