[백준(Baekjoon)] 14235. 크리스마스 선물

 

 

[백준(Baekjoon)] 14235. 크리스마스 선물

 

 

14235번: 크리스마스 선물

 

 

[입력]

 

첫 번째 줄에서는 아이들과 거점지를 방문한 횟수 n이 주어진다.(1≤n≤5,000)

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

 

 

[출력]

 

a가 0일 때마다, 아이들에게 준 선물의 가치를 출력하시오. 만약 줄 선물이 없다면 -1을 출력하라. 적어도 하나의 출력이 있음을 보장한다.

 

 

[풀이]

 

선물의 가치가 큰 것부터 나눠주니까 큐에 저장할때부터 오름차순으로 정렬되게 우선순위큐를 사용한다.

그리고 0일때는 큐가 비어있을 경우 -1을 출력하고 큐에 선물이 있을 경우 꺼내 출력한다.

0이 아닌 양수일 경우에는 뒤에 거점을 들러서 선물을 offer한다.

 

 

 

[코드]

 

public class bj14235 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
		//우선순위큐 오름차순
        
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			if(a == 0) { //0일때 나눠줌
				if(q.isEmpty()) { //큐가 비어있으면 줄게 없어서 -1
					System.out.println(-1);
				}else { //큐에 선물 있으면 출력
					System.out.println(q.poll());
				}
			}else { //0이 아닐때는 선물 담음
				for (int j = 0; j < a; j++) {
					int present = Integer.parseInt(st.nextToken());
					 q.offer(present);
				}
			}
		}
	}

}