백준 23843 콘센트 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/23843


풀이는 다음과 같다.
주석의 예시는
5 2
1 4 4 8 1
이 입력되었을때이다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st1.nextToken()); //5
        int M = Integer.parseInt(st1.nextToken()); //2

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        Long[] time = new Long[N];
        for(int i = 0 ; i < N ; i++) {
            time[i] = Long.parseLong(st2.nextToken()); // 1 4 4 8 1
        }
        Arrays.sort(time, Collections.reverseOrder()); //내림차순 정렬
        //8 4 4 1 1

        PriorityQueue<Long> q = new PriorityQueue<>();

        long max = 0;
        
        if(N > M) { //전자기기가 콘센트보다 많을때
        
        	//큐에 콘센트의 개수만큼만 넣기
            for(int i = 0 ; i < M ; i++) { // 8 4 큐에 넣기
                q.add(time[i]);
            }

			//가장 한가한 큐를 뽑아서 
            //용량이 큰 순서대로 남은 전자기기 할당시키기
            for(int i = M ; i < N ; i++) { //8 4를 큐에 넣은 후 우선순위 큐에서 뽑고(작은수 먼저 나와서 크게 만들 예정) 시간 더해주고 다시 넣기
                long now = q.poll();
                long next = now + time[i];
                q.add(next);
            }

            //여기까지 오면, 우선순위 큐엔 M개만 담겨있음, 가장 큰값은 큐의 맨 처음에 들어가있음
            
            for(int i = 0 ; i < M ; i++) {
                if(i != M-1) {
                    q.poll();
                }
                else { //최댓값
                    max = q.poll();
                }
            }
            
            //처음에 우선순위 큐에 콘센트 개수만큼 넣어준다.
            //8 4 4 1 1 에서, 콘센트는 두개니까 8과 4를 넣는다.
            // 큐 : 8 4 (남은거 4 1 1)
            // 큐의 두 숫자중 작은 숫자 4를 뽑고, 
            // 남은것중 가장 큰것 4와 더해준다
            // 그렇다면 8이 되고, 다시 큐에 넣어준다
            // 그렇게 아래의 8 8이 되는것.
           
            
        	//큐 : 8 8 (남은거 1 1)
            // 큐의 두 숫자중 작은 숫자 8을 뽑고, 
            // 남은것중 가장 큰것 1과 더해준다
            // 그렇다면 9가 되고, 다시 큐에 넣어준다
            // 그렇게 아래의 9 8이 되는것.
            
        	//9 8 (마찬가지 로직)
        	//9 9, 이 순서대로 변하게 됨 (위에서부터 주석으로  쭉 설명되어 내려옴)
            
            //해당 내용이 다 끝나게 되면, 
            //큐의 맨 마지막에는 
            //가장 일이 많은 콘센트가 해야 할 일의 시간이 남게 된다
            
        }
        else { //전자기기가 콘센트보다 적거나 같을때
            max = time[0];
        }

        

        

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
    }

}

내가 계속 바로 아래에 있는 블럭 부분만 구현하고,
내가 가진 전자기기보다 콘센트가 더 많을때는 고려해주지 않았다.
문제를 다시 가서 보니까, N >= M이다 라는 조건은 어디에도 없었다.
그래서 ArrayOutOfIndex 에러가
제출하면서 세번이나 걸리는데,
이유를 알기 전까지 다시봐도 틀린부분이 없어 조금 답답했다.
항상 느끼는건데,
문제는 시간 다다익선으로 투자해서 꼼꼼하게 읽자!

for(int i = 0 ; i < M ; i++) { // 8 4 큐에 넣기
                q.add(time[i]);
            }

            for(int i = M ; i < N ; i++) { //8 4를 큐에 넣은 후 우선순위 큐에서 뽑고(작은수 먼저 나와서 크게 만들 예정) 시간 더해주고 다시 넣기
                long now = q.poll();
                long next = now + time[i];
                q.add(next);
            }

            //여기까지 오면, 우선순위 큐엔 M개만 담겨있음, 가장 큰값은 큐의 맨 처음에 들어가있음
            
            for(int i = 0 ; i < M ; i++) {
                if(i != M-1) {
                    q.poll();
                }
                else { //최댓값
                    max = q.poll();
                }
            }

아, 그리고,
이번 문제와 같이
숫자들이 주어지고,
해당 숫자들을 가장 균등하게 정해진 수의 집합으로 배분하는 방법은
우선순위 큐를 이용하면 쉽다.
(주석을 잘 읽어보면 무슨 내용인지 이해가 가실듯.)


우선순위 큐를 구현한 후,
큐의 가장 앞에있는 콘센트(충전 해야하는 숫자가 가장 작은 콘센트)를 뽑아서 해당 친구에게 전자기기(time[i])를 할당해주는
그리디 알고리즘같은 느낌이다.