아이들과 선물 상자

문제

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

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

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

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

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

입력

첫째 줄에 선물 상자의 수 $N$ 과 아이들의 수 $M$이 공백을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ $1\le M \le N\le 10^5$)

둘째 줄에 각 선물 상자에 들어있는 선물의 개수 $c_1,c_2,\ldots ,c_N$이 공백을 사이에 두고 주어진다. ($1\le c_i\le 10^5$)

셋째 줄에 아이들의 번호 순으로 각 아이가 원하는 선물의 개수 $w_1,w_2,\ldots ,w_M$이 공백을 사이에 두고 주어진다. ($1\le w_i\le 10^5$)

출력

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

예제 입력 1

4 4
4 3 2 1
3 1 2 1

예제 출력 1

1

예제 입력 2

4 3
4 3 2 1
3 1 5

예제 출력 2

0

문제 풀이

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

public class BJ23757 {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());

        PriorityQueue<Integer> gift=new PriorityQueue<>(Collections.reverseOrder());
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            gift.add(Integer.parseInt(st.nextToken()));
        }

        int[] want=new int[M];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++){
            want[i]=Integer.parseInt(st.nextToken());
        }

        boolean flag=false;
        for(int i=0;i<M;i++){
            int g=gift.poll();
            int w=want[i];

            if(g>w){
                gift.add(g-w);
            }else if(g<w){
                flag=true;
                break;
            }
        }

        if(!flag){
            System.out.println(1);
        }else{
            System.out.println(0);
        }
    }
}

M명의 아이들이 모두 선물을 받아갈 수 있는지 판단해야하는 문제로 가장 많은 선물이 들은 상자부터 선물을 가져간다.

즉, 선물 개수가 많은 상자 순서대로 정렬을 해야하는 것이다.

하지만 한 번 꺼낸 상자는 또 다시 꺼낼 수 있기 때문에 남아있는 선물의 개수를 줄여 또다시 정렬을 해야하기 때문에 시간이 걸린다.

이때 우선순위큐를 사용하여 시간복잡도를 줄일 수 있다.

우선순위큐로 선물 개수 갱신하기

PriorityQueue<Integer> gift=new PriorityQueue<>(Collections.reverseOrder());
st=new StringTokenizer(br.readLine());
for(int i=0;i<N;i++){
    gift.add(Integer.parseInt(st.nextToken()));
}

PriorityQueue를 이용하여 gift라는 우선순위큐를 만들어주는데 가장 많은 선물을 가진 상자부터 꺼내야하므로 Collections.reverseOrder()를 이용하여 내림차순으로 정렬하도록 선언하면 이후에 값을 추가해도 내림차순으로 정렬이 될 것이다.

boolean flag=false;
for(int i=0;i<M;i++){
    int g=gift.poll();
    int w=want[i];
    
    if(g>w){
        gift.add(g-w);
    }else if(g<w){
        flag=true;
        break;
    }
}

우선순위큐에서 가장 많은 선물이 들어있는 선물 상자를 꺼내고 현재 순서에 있는 아이가 원하는 상자 개수보다 많다면 선물을 빼내고 남은 값만 다시 큐에 넣어준다.

만약 원하는 선물 개수보다 적게 있다면 실망하게되기 때문에 for문을 break를 통해 탈출하여 0을 출력한다.

주의할 점

처음에 문제를 잘못 파악해서 선물을 원하는 아이들의 순서가 정해져있지 않다고 판단하여 아이들의 정보 또한 우선순위큐에 넣어 코드를 짰다.

제출을 하면 바로 틀려서 구글링을 했더니 아이들의 순서는 정해져있는 상황이었다.

1번 아이부터 M번 아이까지 한 번에 한 명씩, 현재 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물을 가져간다. 

이 문장이 1번부터 M번까지 순서대로 선물을 가져간다는 뜻을 의미한 것 같다.

문제를 제대로 읽고 이해하는 실력이 필요한 것 같다.