백준 23757: 아이들과 선물 상자(java)

문제

---

풀이

 

우선순위 큐를 사용해 쉽게 해결할 수 있다.

 

선물이 가장 많이 담겨있는 상자부터 열어야 하므로 최대 우선순위 큐를 사용하고, PriorityQueue 객체 생성 시 내림차순 정렬을 위해 Comparator.reverseOrder()을 지정한다.

 

누군가 선물을 가져갔던 상자에서 또다시 가져가도 된다는 점에만 주의하면 된다. 원하는 만큼(n) 선물을 가져간 후(poll) 남은 상자는 다시 정렬에 포함시켜야 하므로(add) 아래와 같이 작성할 수 있다.

queue.add(queue.poll()-n);

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Integer> queue=new PriorityQueue<>(Comparator.reverseOrder());
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		
		st=new StringTokenizer(br.readLine());	//queue에 삽입
		for(int i=0; i<N; i++) {
			queue.add(Integer.parseInt(st.nextToken()));
		}
		
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			int n=Integer.parseInt(st.nextToken());
			
			if(queue.peek()<n) {	//실망하면
				System.out.println(0);
				return;	//바로 종료
			}
			
			queue.add(queue.poll()-n);
		}
		
		System.out.println(1);
	}
}

프로그램 효율을 위해, 한 명이라도 실망하면 이후의 반복으로 진행하지 않고 바로 종료하도록 했다.