[백준] 아이들과 선물상자

 

시간복잡도 생각해보기

• 10의 최대가 5승이기 때문에 O(NM)으로 풀수 없고 O(NlogM)으로 풀어야 하는 문제였음.
• 반복문 M번 동안 우선순위 큐를 사용하고 정렬하므로 O(MlogN)풀이 아이디어
• 계속 최신으로 큰 값을 갱신해줘야 해서 우선순위 큐 사용
• M번 반복문 돌리며 아이들이 원하는 값보다 선물상자에 있는 값이 작으면 바로 0 리턴
• 만약 무사히 M번동안 선물 조건이 충족했다면 1리턴

의사코드 / 풀이 과정

for(int i=0; i<M; i++) {
    int maxBox = hpq.poll();
    int give = Integer.parseInt(st.nextToken());
    if(maxBox < give) {
        System.out.println(0);
        return;
    }
    if(maxBox>give) { //선물이 남았으면 
        hpq.add(maxBox - give);
    }
}    

틀린코드, 틀린이유

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

public class Main {
    static PriorityQueue<Integer> hpq = new PriorityQueue<>(Collections.reverseOrder());
    static PriorityQueue<Integer> gpq = new PriorityQueue<>(Collections.reverseOrder());
    static int answer = 1;
    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());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            hpq.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) {
            gpq.add(Integer.parseInt(st.nextToken()));
        }
        while(!gpq.isEmpty()) {
            int maxBox = hpq.poll();
            int give = gpq.poll();
            if(maxBox < give) {
                answer = 0;
                break;
            }
            if(maxBox>give) { //선물이 남았으면 
                hpq.add(maxBox - give);
            }
        }            
        System.out.println(answer);
    }
}

틀린이유

아이들의 선물 값도 우선순위 큐에 담고 그거마저 O(logN)의 정렬을 할 필요 없이 순번대로 줘야함.
따라서 맘대로 아이들의 순번을 정렬하고 순번 바꾸면 안 된다.