Baekjoon 23757 아이들과 선물 상자 JAVA

23757번: 아이들과 선물 상자

문제

상훈이는 N$N$개의 선물 상자를 가지고 있다. 선물 상자에는 현재 담겨있는 선물의 개수가 적혀있다.

선물을 받을 아이들이 M$M$명 있다. 아이들은 각자 1$1$에서 M$M$까지의 서로 다른 번호를 하나씩 부여받았다.

 1$1$번 아이부터 M$M$번 아이까지 한 번에 한 명씩, 현재 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물을 가져간다. 이 때, 앞서 누군가 선물을 가져갔던 선물 상자에서 또다시 가져가도 상관없다.

하지만 상자에 자신이 원하는 것보다 적은 개수의 선물이 들어있다면, 선물을 가져가지 못해 실망한다.

상훈이는 한 명이라도 실망하지 않고 모두가 선물을 가져갈 수 있는지 궁금하다.

입력

첫째 줄에 선물 상자의 수 N 과 아이들의 수 M이 공백을 사이에 두고 주어진다. (1 <= M <= N <= 10^5)
둘째 줄에 각 선물 상자에 들어있는 선물의 개수 c1, c2, ... cn이 공백을 사이에 두고 주어진다. (1<= ci <= 10^5)

셋째 줄에 아이들의 번호 순으로 각 아이가 원하는 선물의 개수 w1, w2, ... wm이 공백을 사이에 두고 주어진다. (1<= wi<= 10^5)

출력

모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 1을, 그렇지 않으면 0을 출력한다.

풀이

우선순위 큐를 이용하여 항상 가장 많은 사탕을 가지는 상자를 유지함.

각 아이들이 요구하는 선물을 가져간다.

이 때 가장 많은 사탕을 들고 있는 상자에서 가져갈만큼의 사탕을 뺀 후 다시 큐에 넣어서

상자의 순서를 유지시킨다.

for문을 이용해서 가장 마지막 아이까지 사탕을 가져간다면 1을 출력, 가져가지 못하면 0을 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), i=0;
		PriorityQueue<Integer> gift = new PriorityQueue<Integer>(Collections.reverseOrder());
		// 선물은 지속적으로 가장 큰 선물 상자를 이용하기에 우선순위큐를 내림차순으로 이용하여 head부분에 항상 가장 큰 선물 개수가 오도록 함
		int [] child = new int[m];
		// 학생들은 부여된 순서대로 선물을 챙김

		st = new StringTokenizer(br.readLine());
		for(i=0;i<n;i++)
			gift.add(Integer.parseInt(st.nextToken()));
		st = new StringTokenizer(br.readLine());
		for(i=0;i<m;i++)
			child[i] = Integer.parseInt(st.nextToken());
		i=0;
		while(i<m && gift.size()>0) {
			if(child[i]==gift.peek()) {	// 학생이 원하는 선물의 개수와 현재 최대 선물 개수가 동일하다면 학생번호를 증가시키고 선물을 삭제
				i++;
				gift.poll();
			}else if(child[i]<gift.peek())	// 최대 선물 개수가 더 크다면 선물을 가져가고 남은 선물을 다시 큐에 삽입 
				gift.add(gift.poll()-child[i++]);
			else	// 선물을 못가져 간다면 아이들이 실망하면서 종료
				break;
		}
		if(i==m)	// 학생들이 증가해서 마지막학생까지 선물을 가져갔다면 1을 출력
			System.out.println(1);
		else
			System.out.println(0);
	}
}