[Programmers] 야근 지수 (Java)

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

프로그래머스

 

---

숫자의 범위가 큰 수를 처리해야 하므로 일일이 처리하는 게 아니라 그리디라고 착각했다. 쉽게 구할 수 있는 수식이 있을 거라고 생각해 잘못된 생각을 했다.

남은 작업량을 모두 더해 일을 최대한 한 뒤 남은 일에 고르게 분배했다. 하지만 이러면 일이 한 쪽에 치우쳐져 있을 경우를 생각하지 못한다.

그래서 일일이 처리할 수 밖에 없다는 생각이 들었다.

알고리즘

아주 간단하게 생각했을 때 O(N^2)은 가능했다. 위의 내 생각은 O(N)인데 불가능했다. 따라서 O(NlogN)이겠다는 생각이 들었다.

logN 이 들어가는 것은 그리 많지 않다. 이진 탐색과 트리 정도이다. 따라서 트리 모양의 우선순위 큐를 사용했다.

 

작업량들을 모두 역순으로 정렬해 넣었다. 시간이 다 될때까지 제일 작업이 많이 남은 것을 꺼내 1을 빼고 다시 넣었다.

그리고 남은 작업량을 모두 제곱해서 더했다.

정답코드

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for (int work : works) {
            q.offer(work);
        }
        for (int i = 0; i < n; i++) {
            int work = q.poll();
            if (work == 0) break;
            q.offer(work-1);
        }
        while (!q.isEmpty()) {
            int work = q.poll();
            answer += work * work;
        }
        return answer;
    }
}