백준 1966: 프린터 큐(java)

문제

---

풀이

LinkedList를 이용해 프린터를 표현했다.

LinkedList<int[]> list=new LinkedList<>();

 

list의 요소는 int형 1차원 배열로 하여 아래와 같이 문서의 인덱스와 중요도를 저장한다.

N과 M을 입력받고, for문을 이용하여 list에 값을 넣으면 아래와 같은 초기 상태를 완성할 수 있다.

for(int j=0; j<N; j++) {
	list.offer(new int[] { j, Integer.parseInt(st.nextToken())});
}

예시 3

 

현재 문서보다 중요도가 높은 문서가 하나라도 있다면 그 문서를 먼저 출력해야 하므로, 인덱스가 0일 때부터 1씩 증가시키며 비교해야 한다. 

int[] current=list.poll();
boolean isMax=true;

우선 현재 문서를 저장할 int형 current 배열과 현재 문서의 중요도가 최대인지를 나타내는 boolean형 변수 isMax를 선언한다. current와 isMax는 매 반복마다 갱신되어야 하므로, 위 선언문들은 반복문 최상단에 작성해야 한다.

 

이제 list 내에서 처음으로 current보다 중요도가 높은 요소를 마주칠 때까지 for문을 순회한다.

for(int j=0; j<list.size(); j++) {
	if(current[1]<list.get(j)[1]) {	//현재 요소보다 j번째 요소의 중요도가 클 때
		list.offer(current); //현재 요소를 list 가장 뒤에 재배치
						
		for(int k=0; k<j; k++) {	//current의 다음 요소부터 current보다 처음으로 큰 요소 전까지의 모든 요소를
			list.offer(list.poll());	//list 가장 뒤로 보냄
		}
						
		isMax=false;	//current의 중요도가 최대가 아니었으므로 isMax=false
		break;
	}
}

if(isMax==false) {
	continue;
}

//isMax가 계속 true일 경우
count++;
if(current[0]==M) {
	break;
}

j=2일 때

 

이후 int[2]가 current가 되고, isMax=true로 재설정된다. current 이후로 current보다 중요도가 높은 요소가 없으므로 current는 list에 다시 삽입되지 않은 채 넘어가고, count를 1 증가시킨다. 이때 count는 목표한 요소가 출력되기까지 몇 개의 요소가 먼저 출력되었는지(=목표의 순서)를 나타낸다.

이후 남은 요소들에 대해 위 과정을 반복한다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
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 T=Integer.parseInt(br.readLine());
		for(int i=0; i<T; i++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			int N=Integer.parseInt(st.nextToken());
			int M=Integer.parseInt(st.nextToken());
			
			LinkedList<int[]> list=new LinkedList<>();
			
			st=new StringTokenizer(br.readLine());
			
			for(int j=0; j<N; j++) {
				list.offer(new int[] { j, Integer.parseInt(st.nextToken())});
			}
			
			int count=0;
			
			while(!list.isEmpty()) {
				int[] current=list.poll();
				boolean isMax=true;
				
				for(int j=0; j<list.size(); j++) {
					if(current[1]<list.get(j)[1]) {	
						list.offer(current);
						
						for(int k=0; k<j; k++) {
							list.offer(list.poll());
						}
						
						isMax=false;
						break;
					}
				}
				
				if(isMax==false) {
					continue;
				}
				
				count++;
				if(current[0]==M) {
					break;
				}
			}
			
			sb.append(count).append("\n");
		}
		
		System.out.println(sb);
	}
}