[백준_14235번] 크리스마스 선물

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

14235번: 크리스마스 선물

[문제]

 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다. 또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.

 이제 산타가 선물을 나눠줄 것이다. 차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들이 준 선물들의 가치들을 출력하시오. 만약 아이들에게 줄 선물이 없다면 -1을 출력하시오.

 

[입력 조건]

• 첫 번째 줄에서는 아이들과 거점지를 방문한 횟수 n이 주어진다.(1≤n≤5,000)
• 다음 n줄에는 a가 들어오고, 그 다음 a개의 숫자가 들어온다. 이는 거점지에서 a개의 선물을 충전하는 것이고, 그 숫자들이 선물의 가치이다. 만약 a가 0이라면 거점지가 아닌 아이들을 만난 것이다. 선물의 가치는 100,000보다 작은 양의 정수이다.(1≤a≤100)

 

[코드]

import java.util.*;

public class BaekJoon_14235 {
	static PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());
	static int n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		
		while(n-->0) {
			int a=sc.nextInt();
			
			// a가 0이면 아이에게 가장 가치가 큰 선물 하나를 선물
			if(a==0) {
				// 만약 설매가 비었다면 -1 출력
				if(pq.isEmpty())
					System.out.println(-1);
				// 선물이 있다면 우선순위가 높은 선물 출력&삭제
				else
					System.out.println(pq.poll());
			}
			// a가 0이 아니라면 a개의 선물 충전
			else {
				for(int i=0;i<a;i++)
					pq.add(sc.nextInt());
			}
		}
	}

}

 

[고찰]

 이번 문제는 어떤 자료구조를 사용할 것이냐가 핵심이었다. 문제에서 힌트가 주어졌는데 "착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다." 이 부분이다.

 배열을 사용하게 되면 완전탐색을 사용하여 매번 가치가 가장 큰 선물을 찾아야하고, 아이에게 선물을 주면 해당 배열 값은 빈 값으로 두거나 이후 배열 값들을 하나씩 앞으로 땡겨야한다. 이렇게되면 메모리와 시간 낭비가 발생하게된다. 이렇게 배열의 단점을 자료구조의 특성으로 해결할 수 있는 것이 바로 우선순위 큐이다. 데이터를 삽입하면 내부에서 값의 크기에 따라 자동 정렬이 되기 때문에 매번 가장 가치가 큰 선물을 가장 먼저 삭제할 수 있다. 

 우선순위 큐를 선언하면 최소힙(크기가 작은 값 부터 우선순위를 갖는다.)으로 만들어진 우선순위 큐가 만들어지기 때문에 Collections.reverseOrder()를 사용하여 최대힙((크기가 큰 값 부터 우선순위를 갖는다.)으로 바꿔 사용하는 편이 효율적이다.