[BOJ] 23843 콘센트 - JAVA

1. 문제

23843번: 콘센트

광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다.

전자기기들은 한 번에 하나의 콘센트에서만 충전이 가능하고, 충전에 필요한 시간은 2k(0 ≤ k ≤ 15, k는 정수) 형태이다.

광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간이 얼마인지 알려주자.

---

2. 풀이

1.  입력받은 수를 정렬한다. (내림차순이면 더 편하지만, Arrays.sort로는 조금 번거로워서 그냥 오름차순으로 했다.)

2.  오름차순으로 정렬되도록 하는 PriorityQueue를 만든다.

3.  queue 사이즈가 M보다 작다면 바로 queue에 offer하고, M과 같다면 queue에서 가장 작은 수를 뽑아서 그 값과 현재 값을 더해서 추가한다. 이 때, 1번의 배열을 오름차순으로 정렬했으므로 끝에서부터 하나씩 체크한다.

4.  다 체크했다면 queue의 가장 마지막 요소를 출력한다.

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

public class BOJ_23843_콘센트 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      //배열 정렬한다
      int[] charge = new int[N];
      st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) charge[i] = Integer.parseInt(st.nextToken());
      Arrays.sort(charge);

      //queue 사이즈=최대 M, 그 요소는 누적합
      PriorityQueue<Integer> queue = new PriorityQueue<>();
      for(int i=N-1;i>=0;i--){
         if(queue.size()<M) queue.offer(charge[i]);
         else queue.offer(queue.poll()+charge[i]);
      }

      //하나빼고 전부 뽑기
      int size = queue.size();
      while(--size>0) queue.poll();

      //출력
      System.out.println(queue.poll());
   }
}

---

3. 결과