[백준] NO.1966 : 프린터 큐

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

본 글에서는 백준 1966번 프린터 큐 문제의 풀이를 설명하며, 문항 정보는 상단의 백준 링크를 통해 확인할 수 있다.

 

1. 문제 분석

이 문제의 핵심은 문서의 중요도에 따라 큐의 원소를 재배치하는 것이다. 이를 해결하기 위해 본인은 다음과 같은 두 가지 자료구조를 사용하였다:

1. 프린트할 순서를 저장하는 큐
2. 문서의 중요도를 저장하는 우선순위 큐

이 두 가지 큐를 통해 문서의 중요도에 따라 적절한 순서로 문서가 프린트되도록 구현하였다.

 

2. 코드 설명

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
/*
 * BOJ NO.1966 : 프린터 큐
 * 	문서의 중요도에 따라 큐의 원소들을 재배치
 * 	=> 프린터 순서 저장하는 큐와 중요도 저장하는 우선순위 큐 사용
 */
	
	// 문서의 정보 담을 내부클래스(static 함수에서 사용하기에 static 클래스 선언)
	static class Document{
		int index; // 문서의 기존 순번
		int importance; // 중요도
		
		public Document(int index, int importance) {
			this.index = index;
			this.importance = importance;
		}
	}
	
	/**
	 * 문서의 중요도에 따라 문서를 출력하는 메서드
	 * @param queue // 프린터 큐
	 * @param importances // 중요도 담은 우선순위 큐
	 * @param targetDocu // 인쇄 순번을 계산할 목표 문서
	 * @return
	 */
	public static int printerQueue( Queue<Document> queue, PriorityQueue<Integer> importances, int targetDocu) {
		// 인쇄 횟수
		int count = 0;
		
		while(!queue.isEmpty()) {
			Document document = queue.peek();
						
			//우선순위 여부 검증
			if(importances.peek() == document.importance) { //우선순위일 경우 바로 프린트
				// 목표 문서가 아닐 경우
				// 큐에서 제거(프린트)
				queue.poll();
				// 우선순위 큐에서 해당 중요도 제거
				importances.poll();
				
				// 인쇄 횟수 증가
				count++;
				
				// 목표 문서일 경우 반복문 종료
				if(targetDocu == document.index) {
					break;
				}
			} else {// 우선순위가 아닐 경우 큐 가장 뒤로 재배치
			   queue.add(queue.poll());
			}
			
		}
		
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 테스트 케이스의 개수 입력 받기
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		while(T-- > 0) {
			
			// 첫째 줄 입력 받기
			String[] firstLine = br.readLine().split(" ");
			//  첫째 줄에서
			// 문서의 개수 N 입력 받기
			int N = Integer.parseInt(firstLine[0]);	
			// 몇 번째로 인쇄됐는지 궁금한 문서가 현재 몇 번째 놓여 있는지 입력 받기
			int M = Integer.parseInt(firstLine[1]);
			
			// 둘째 줄 = N개 문서의 중요도 입력 받기
			String[] secondLine = br.readLine().split(" ");
			
			// 문서들 담을 큐
			Queue<Document> queue = new LinkedList<>();
			
			// 문서의 중요도 담을 우선순위 큐(우선순위 큐는 기본적으로 오름차순 기준이므로 컬렉션 프레임워크의 내장함수 이용해 내림차순 기준으로 생성)
			PriorityQueue<Integer> importances = new PriorityQueue<Integer>(Collections.reverseOrder());
			
			// 중요도 담기
			for(int i = 0; i < secondLine.length; i++) {
				// 중요도 추출
				int importance = Integer.parseInt(secondLine[i]);
				// 우선수위 큐에 삽입
				importances.add(importance);
				// 큐에 넣기(문서의 순서, 중요도)
				queue.add(new Document(i, importance));
			}
			
			sb.append(printerQueue(queue, importances, M)).append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		br.close();
	}
}

 

 

3. 풀이 과정에서 배운 점

 

3. 1. 자바 컬렉션 프레임워크의 제네릭에 기본형 배열 사용 가능

자바의 컬렉션 프레임워크의 제네릭 타입은 객체 타입만 가능하여 기본형 타입은 사용할 수 없으므로, 일반적으로 기본형을 저장할 때는 래퍼 클래스를 사용한다.

 

본 문제 풀이 과정에서도 기본형인 int[] 대신 Integer[]를 사용해 문서의 중요도와 순서를 저장하려 했으나, 오직 숫자만 입력되므로 메모리를 비효율적으로 사용하게 되었다.

 

이를 개선하기 위해 내부 클래스로 Document 클래스를 만들어 해당 클래스의 멤버 변수로 int형 변수를 설정하고 Integer[] 대신 사용할 수 있었다.

 

다만, 클래스 자체의 오버헤드로 인해 결국 메모리 효율을 높이기 위해 기본형 배열 int[]를 사용할 수 있는지 확인해 본 결과, 기본형 배열은 객체로 인식되므로 제네릭 타입으로 사용 가능하다는 사실을 알게 되었다.

 

3.2. 비정적 내부 클래스를 static으로 변경 필요

Document 클래스를 main 메서드에서 사용하려 할 때 다음과 같은 컴파일 에러가 발생하였다.

No enclosing instance of type Main is accessible. Must qualify the allocation with an enclosing instance of type Main (e.g. x.new A() where x is an instance of Main).

 

이 에러의 발생 원인은 다음과 같다:

• main 메서드는 static이기 때문에 메모리의 메소드 영역에 가장 먼저 로드되는데, 이 시점에 비정적 내부 클래스는 메모리에 로드되지 않기 때문에 직접 생성할 수 없다.

이를 해결하기 위해서는 다음의 방안을 사용할 수 있다:

• 비정적 내부 클래스를 static으로 변경하여 외부 인스턴스 없이 직접 생성하거나
• 외부 클래스의 인스턴스를 통해 비정적 내부 클래스 인스턴스를 생성하는 방법을 사용한다.

본 문제에서는 첫 번째 방법을 선택해 Document 클래스를 static으로 선언하여 문제를 해결하였다.