문제 이해

사용 가능한 콘센트 M개가 있고, 이 콘센트를 활용하여 N개의 전자기기를 충전하려 한다.

전자기기는 한 번에 1개의 콘센트에서만 충전 가능하다.
(즉, 완충될 때 까지 1개의 콘센트를 독점함. 다른 전자기기가 해당 콘센트에서 충전 불가)

이 대 모든 전자기기를 충전하기 위한 최소 시간이 얼마일지 구하는 문제이다.

---

문제 풀이

우선순위 큐를 처음으로 제대로 활용했던 문제이다.

개념 자체는 간단하다.

1. 먼저 충전에 걸리는 시간을 정렬한다(순서는 관계 없음)

2. 먼저 N개에 차례대로 M개의 전자기기를 배치시킨다.

3. N개가 찼다면, 충전에 거리는 시간이 가장 작은 값을 Pop한다. 이후, Pop한 값에 충전하지 않은 전자기기 중 가장 큰 값(혹은 작은 값; 정렬을 어떻게 함에 따라 달라짐)을 더해주어 다시 우선수위 큐에 더해준다.

4. 이제 충전시킬 전자기기가 없다면 우선순위 큐 값을 모두 뽑아내서 가장 큰 값을 답으로 출력하면 된다.

예를 들어보자.
1 2 3 4의 충전시간이 걸린다고 가정하자.
이 때 3개의 충전기가 존재한다.

그렇다면 먼저 1, 2, 3짜리를 충전시키고 1짜리 전자기기가 모두 충전되면 그 충전기에다 4짜리 전자기기를 충전시키는 것이 가장 빠른 시간 안에 모든 전자 기기를 충전시키는 것이 될 것이다.

첫 번째 콘센트 입장에서 보면 1 + 4 = 5만큼의 시간이 걸린 것이므로, 우선순위 큐에 (1,2,3) 값이 들어있고 1이 pop 되었을 때 4를 더해 5를 다시 우선순위 큐에 넣어주면 (2,3,5)가 될 것이다.

이제 충전시킬 전자기기가 없으므로, 우선순위 큐에 존재하는 가장 큰 값이 곧 충전이 완료되는 가장 빠른 시간일 것이다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		Integer[] time = new Integer[N];
		
		for(int i =0;i<N;i++) {
			time[i] = sc.nextInt();
		}
		
		Arrays.sort(time, Collections.reverseOrder());
        // 충전 시간을 기준으로 "내림차순"으로 정렬한다.
		
		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		
		int idx = 0;
        // 콘센트에 충전할 전자기기의 Index
        
		while(idx < N) {
			
			if(queue.size()<M) {
            // 충전기를 모두 활용하고 있지 않으므로 전자기기 하나를 추가해준다.
				queue.add(time[idx]);
				idx++;
				continue;
			}
			
			int add = queue.poll() + time[idx];
			queue.add(add);            
            // 우선순위 큐에서 최소값을 빼고, 그 값에 다음으로 충전시킬
            // 전자기기에 소요되는 시간을 더해주어 우선순위 큐에 넣어준다.
            
			idx++;
		}
		
		int answer = -1;
		while(!queue.isEmpty()) {
        // 최종적으로 구하는 시간을 우선순위 큐에 저장된 최댓값이다.
        // 따라서, queue가 비기 전에 마지막으로 출력되는 값이 답이 된다.
			answer = queue.poll();
		}
		
		System.out.println(answer);
	}
	
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과