야근 지수

[antop-dev]

https://school.programmers.co.kr/learn/courses/30/lessons/12927

[antop-dev]

works에 남은 작업량이 큰 것부터 하나씩 차감했다. 가장 많이 남은 작업략을 찾기 위해서 우선순위 큐를 사용했다.

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public long solution(int n, int[] works) {
        long sum = 0L;
        Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> works[o2] - works[o1]);
        for (int i = 0; i < works.length; i++) {
            pq.offer(i);
            sum += works[i];
        }

        if (n >= sum) {
            return 0;
        }

        while (n-- > 0 && !pq.isEmpty()) {
            int poll = pq.poll();
            works[poll]--;
            pq.offer(poll);
        }

        long ans = 0L;
        for (int v : works) {
            sum += v;
            ans += (long) v * v;
        }
        return ans;
    }
}

[antop-dev]

우선순위 큐에 인덱스를 넣지 않고, 값을 넣어서 하는 방법도 있다.

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public long solution(int n, int[] works) {
        Queue<Integer> pq = priorityQueue(works);
        work(pq, n);
        return fatigue(pq);
    }

    private Queue<Integer> priorityQueue(int[] works) {
        Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int v : works) {
            pq.offer(v);
        }
        return pq;
    }

    private void work(Queue<Integer> queue, int n) {
        while (n-- > 0 && !queue.isEmpty()) {
            int v = queue.poll();
            if (v > 0) v--;
            queue.offer(v);
        }
    }

    private long fatigue(Queue<Integer> queue) {
        long fatigue = 0L;
        while (!queue.isEmpty()) {
            int v = queue.poll();
            fatigue += (long) v * v;
        }
        return fatigue;
    }
}