[백준] 콘센트 - Java 23843

https://www.acmicpc.net/problem/23843

 

 

콘센트의 차징 시간을 내림차순으로 정렬하는 것이 키 포인트인 문제이다.

 

내림차순으로 정렬한 뒤 시간을 1씩 늘려가며 `sumpq.peek()`의 값이 `time`보다 작거나 같으면

`sumpq`에서 해당 값을 빼주고 내림차순으로 정렬된 `pq`에서 값을 뽑아

time을 더해 새롭게 `sumpq`에 더한다.  

 

 

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

public class BOJ23843 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
        PriorityQueue<Integer> sumpq = new PriorityQueue<>();

        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++){
            pq.add(Integer.parseInt(st.nextToken()));
        }

        for(int i = 0; i < M; i++){
            if(!pq.isEmpty())
                sumpq.add(pq.poll());
        }

        int time = 0;

        int count = 0;
        while(!sumpq.isEmpty()){
            time++;
//            int count = 0;
            while(!sumpq.isEmpty() && time >= sumpq.peek()){
//                count++;
                sumpq.poll();

                if(!pq.isEmpty()) {
                    sumpq.add(time + pq.poll());
                }
//                System.out.println(time);
            }
//            System.out.println(time);
//            System.out.println(pq);
        }

        System.out.println(time);
    }
}

// 5 2
// 1 1 1 4 4 8