백준(Backjoon) 1966, 프린터 큐

문제풀이

위 문제를 해결하기 위해서 Node 클래스를 정의하였다. Node 클래스는 id와 priority 정수형 필드를 가지고 있다. id 필드를 정의한 이유는 지정한 문서가 몇 번째로 인쇄되었는지 알기 위해서이다. 이 글에서는 해당 변수를 target이라 정의하였다. priority 필드를 활용하여 알지 못하는 이유는 priority 필드는 중복이 가능하기 때문이다.

 

문제핵심

• 큐 구조의 맨 앞에 존재하는 인쇄하고자 하는 문서가 다른 문서들보다 우선순위(priority)가 제일 높은지 검사하는 것
• 만약 맨 앞의 인쇄 문서가 다른 문서들보다 우선순위가 작은 경우 큐 구조 맨 뒤로 보내야 하는 것
• 마지막으로 우선순위가 제일 높아 큐 구조에서 제거될때 제거된 문서의 id가 몇 번째로 인쇄되었는지 궁금한 target 변수와 동일한지 검사하는 것

이 글에서는 List<Node>로 선언한 printer 리스트를 반복문을 통하여 우선순위가 제일 높은지 검사하였다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;



public class Main {
	
	static class Node{
		int priority;	// 중요도
		int id;			// 문서 id
		
		public Node(int priority, int id) {
			this.priority = priority;
			this.id = id;
		}

		@Override
		public String toString() {
			return "Node [priority=" + priority + ", id=" + id + "]";
		}
		
		

	}
	
	public static int solution(List<Node> printer, int target)
	{
		int count=0;
		while(!printer.isEmpty())
		{
			Node node = printer.get(0);
			
			/* node보다 높은 우선순위를 가진 다른 node가 있는지 탐색한다. */
			boolean flag = false;
			for(int i=1;i<printer.size();i++)
			{
				if(node.priority<printer.get(i).priority)
				{
					flag = true;
					break;
				}
			}
			/* flag==true이면 node보다 높은 우선순위의 문서가 있는 것이므로 리스트의 뒤로 보낸다.*/
			printer.remove(0);
			if(flag==true)
			{
				printer.add(node);
			}else
			{
				count++;
				if(node.id==target)
				{
					return count;
				}
			}
		}
		return count;
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());		// 테스트케이스 개수
		
		for(int t=0;t<tc;t++)
		{
			String[] str = br.readLine().split(" ");
			int N = Integer.parseInt(str[0]);		// 문서 개수
			int target = Integer.parseInt(str[1]);	// 몇번째로 인쇄하는지 궁금한 문서id
			int[] nodes = new int[N];
			str = br.readLine().split(" ");
			for(int i=0;i<nodes.length;i++)
			{
				nodes[i] = Integer.parseInt(str[i]);
			}
			
			
			List<Node> printer = new ArrayList<>();
			
			for(int i=0;i<N;i++)
			{	
				printer.add(new Node(nodes[i],i));
			}
			
			
			System.out.println(solution(printer, target));
		}
	}
}

 

우선순위 큐를 활용한 문제풀이

위의 문제풀이에서 printer 리스트에서 꺼낸 노드의 우선순위가 제일 높은 우선순위인지 확인하기 위하여 반복문을 통하여 검사하였다. 하지만 우선순위 큐 개념을 활용하여 maxHeap을 구성하면 우선순위 큐에는 우선순위 변수가 내림차순으로 정렬되어 구성된다.

즉, printer 리스트에서 꺼낸 노드의 우선순위 정수값과 우선순위 큐의 루트 노드인 우선순위 값이 같은 경우에만 카운트하고 id를 비교하면 된다.

 

소스코드

public class Main {
	static class Node{
		int priority;	// 중요도
		int id;			// 문서 id
		
		public Node(int priority, int id) {
			this.priority = priority;
			this.id = id;
		}

		@Override
		public String toString() {
			return "Node [priority=" + priority + ", id=" + id + "]";
		}

	}

	public static int solution(List<Node> printer, PriorityQueue<Integer> prioritys, int target)
	{
		int count=0;
		while(!printer.isEmpty())
		{
			Node node = printer.remove(0);
			
			// printer 큐의 맨 앞에 있는 문서의 우선순위가 prioritys 우선순위큐의 제일 앞에 있는 우선순위와 같은지 검사
			if(node.priority==prioritys.peek())
			{
				prioritys.poll();
				count++;
				if(node.id==target)
				{
					break;
				}
			}
			else
			{
				printer.add(node);
			}
		}
		return count;
	}
	
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());		// 테스트케이스 개수
		
		for(int t=0;t<tc;t++)
		{
			String[] str = br.readLine().split(" ");
			int N = Integer.parseInt(str[0]);		// 문서 개수
			int target = Integer.parseInt(str[1]);	// 몇번째로 인쇄하는지 궁금한 문서id
			
			str = br.readLine().split(" ");
			
			List<Node> printer = new ArrayList<>();
			PriorityQueue<Integer> prioritys = new PriorityQueue<Integer>(Collections.reverseOrder());
			
			
			for(int i=0;i<N;i++)
			{	
				printer.add(new Node(Integer.parseInt(str[i]),i));
				prioritys.add(Integer.parseInt(str[i]));
			}
			System.out.println(solution(printer, prioritys, target));
			
		}
	}
}

 

References

[백준] 1966번 C/C++ 풀이_프린터 큐, http://melonicedlatte.com/algorithm/2018/02/18/230705.html