[프로그래머스, 12927] 야근 지수 (java)

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

프로그래머스

728x90

---

메모리: 86.4 MB, 시간: 217.07 ms

사용 알고리즘: 자료구조

 

무조건 작업량이 많은 작업의 크기를 줄이는 것이 유리하다.

따라서 PriorityQueue에 내림차순으로 정렬하여, 현재 작업량이 가장 많이 남은 작업을 꺼내서 1씩 처리하는 과정을 n번 거치면 최소값을 구할 수 있다.

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        
        // 내림차순 정렬을 위한 pq
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
        
        // 남은 작업량을 내림차순 정렬
        for(int i = 0; i < works.length; i++) {
            pq.add(works[i]);
        }
        
        // 가장 작업량이 많이 남은 작업부터 꺼내서 처리
        int w;
        for(int i = 0; i < n; i++) {
            w = pq.poll() - 1;
            
            // 해당 작업을 끝냈다면 다시 넣지 않음
            if(w > 0) pq.add(w);
            
            // 더 이상 처리할 작업이 없다면 끝냄
            if(pq.isEmpty()) break;
        }
        
        // 피로도 구하기
        long answer = 0;
        while(!pq.isEmpty()) answer += Math.pow(pq.poll(), 2);
        
        return answer;
    }
}