[프로그래머스/LV3] 야근지수 - PriorityQueue(Java)

[프로그래머스/LV3] 야근지수

🙋‍♂️ 들어가며

이 문제는 pq를 활용해 푸는 문제로 먼저 pq 동작방식과 연산횟수를 이해할 필요가 있다.

만약 내림차순 pq로 정의하고, 길이가 M인 원소를 추가하면 가장 큰 원소만 맨 앞에 배치되고 나머지는 정렬을 따르지는 않는다.

예시다

arr = {1, 6, 7}
pq = {7, 1, 6}

pq의 시간복잡도는 다음과 같다 M log M

ex) M = 100

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

// 2. M*log(M)
int M = arr.length;
for (int i = 0; i < M; i++) {
    pq.add(arr[i]);
}

최악의 연산은 100 * log 100 인데 100은 1중 for문이고, log 100은 pq가 내림차순이지만, 정렬을 하기에 log100이 필요한 것이다.

거두절미하고 이 문제를 읽어보면

내림차순 pq를 통해 n만큼 반복하여 제일 큰 값을 1씩 빼는 코드이다.

최악의 경우 ( 2만 * log(2만) ) + ( 100만 * log(2만) )

tc-1

arr = {1, 6, 7}
n = 5

tc-2

arr = {1, 1, 10}
n = 6

✅ 코드 (pq)

import java.util.PriorityQueue;
import java.util.Collections;


class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        
        // 0. 조기종료 (n >= 배열의 합)
        long temp_sum = 0;
        for (int w : works) {
            temp_sum += w;
        }
        if (temp_sum <= n) return 0;
        
        
        // 1. 내림차순 pq (가장큰 원소만 내림차순 정렬, 나머지는 정렬X)
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        // 2. M*log(M)
        int M = works.length;
        for (int i = 0; i < M; i++) {
            pq.add(works[i]);
        }
        
        // 3. n만큼 빼기 100만 * log(2만) -> 최악의 경우 약 1400만
        int cnt = 0;
        while (cnt < n) {
            int max_val = pq.poll();
            int new_val = max_val-1;
            pq.offer(new_val);
            cnt++;
        }
        
        // 4. 답 계산
        while (!pq.isEmpty()) {
            int val = pq.poll();
            answer += (val * val);
        }
        return answer;
    }
}