백준 23757 java : 우선순위큐

왜 시간, 메모리 효율성이 떨어지는가?

1. Scanner 사용 -> BufferedReader로 수정해야 함
2. w자료구조를 굳이 큐로 할 필요는 없는거 같다. 배열로 해도 되고, c를 미리 입력받으니 w자료구조를 만들지 않고 입력과 동시에 수행해도 된다.

왜 우선순위 큐를 사용했는가?

우선순위 큐는 큐처럼 조회순서를 정할 수 있고, 추가로 정렬 순서도 정할 수 있어서, 문제풀이에 최적화된 자료구조다.

import java.util.*;

public class bj23757 {
    static Scanner sc = new Scanner(System.in);
    static int N, M;
    //static int[] c;
    //static int[] w;
    static PriorityQueue<Integer> c;
    static Queue<Integer> w;

    public static void main(String[] args) {
        inputData();
        System.out.println(findAnswer());

        sc.close();
    }

    public static void inputData() {
        int i;

        N = sc.nextInt();//선물 상자 개수
        M = sc.nextInt();//선물을 받을 아이들 수

        //c = new int[N];
        c = new PriorityQueue<>(Collections.reverseOrder());
        //w = new int[M];
        w = new LinkedList<>();

        for (i = 0; i < N; i++) {
            //c[i] = sc.nextInt();//각 선물 상자 안에는 선물이 여러개 들어 있음
            c.offer(sc.nextInt());//각 선물 상자 안에는 선물이 여러개 들어 있음
        }
        for (i = 0; i < M; i++) {
            //w[i] = sc.nextInt();//각 아이들은 원하는 선물 개수가 다름
            w.offer(sc.nextInt());//각 아이들은 원하는 선물 개수가 다름
        }
    }

    public static int findAnswer() {
        int answer = 1;

        //한 번에 한 명씩, 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물 가져가기
        //우선순위큐 사용해야 할 듯
        while(!w.isEmpty()) {
            if(w.peek() <= c.peek()) {
                int temp = c.poll() - w.poll();
                System.out.println(temp);

                if(temp == 0){
                    System.out.println("상자 내에서 해결 후 다 털음");
                    continue;
                }
                else{
                    System.out.println("상자 내에서 해결 가능");
                    c.offer(temp);
                }
            }
            else{
                System.out.println("더 이상 가져갈 수 없음");
                answer = 0;
                break;
            }
        }

        return answer;
    }
}