[백준/BOJ][JAVA] 23757 - 아이들과 선물상자

[문제 풀러 가기]

23757번: 아이들과 선물 상자

📘 문제

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

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

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

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

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

📘 문제풀이

선물상자에 들어갈 값을 Priority Queue에 내림차순으로 담아 아이들이 원하는 선물의 개수를 선물함에 있는 상자가 아이들이 원하는 선물의 개수보다 크거나 같으면 선물함 개수 - 아이들이 원한 선물 개수를 해 다시 Priority Queue에 넣으며 계산하는 방식을 사용했다.

📘 소스코드

package BOJ.Queue;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj23757_아이들과선물상자 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> present = new PriorityQueue<>(Collections.reverseOrder());

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            int value = Integer.parseInt(st.nextToken());
            present.offer(value);

        }
        st = new StringTokenizer(br.readLine(), " ");
        boolean flag = false;
        for (int i = 0; i < M; i++) {
            int child = Integer.parseInt(st.nextToken());
            if (present.peek() >= child) {
                present.offer(present.peek() - child);
                present.poll();
            } else {
                flag = true;
            }
        }

        if (flag == true) {
            sb.append("0");
        } else {
            sb.append("1");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

📘 내 리뷰

내 제출

 

---

처음엔 배열로 그다음엔 Queue로 풀었는데 모두 시간 초과가 떠서 Priority Queue를 생각해내게 되었다.
모두 같은 방식으로 풀었지만 Priority Queue를 쓰니 바로 시간 초과 해결... 삽질을 엄청 했던 문제였다.

🤕🤕🤕🤕