프로그래머스 야근 지수 자바 풀이

문제 요약

남은 작업량 배열 works와 일할 수 있는 시간 n이 주어진다
매 시간 작업량 하나를 1만큼 줄일 수 있다
야근 피로도는 남은 작업량들의 제곱의 합이다
n시간을 모두 사용해 피로도를 최소화한 값을 구한다

문제 풀이

처음에는 매 시간마다 배열을 순회해서 가장 큰 작업량을 찾아 1을 깎는 방식을 생각했다.

하지만 이 방식은 시간 안에 끝나지 않는다.

n은 최대 1,000,000이고 works의 길이는 최대 20,000인데, 매 시간마다 배열 전체를 훑어 최댓값을 찾으면 전체 연산량이 n * works.length, 최악의 경우 2 * 10^10에 가까워진다.

이 문제의 핵심은 매 시간 가장 큰 작업량 하나를 최대 힙에서 꺼내 1을 깎고 다시 넣는 것이다.

배열 전체를 매번 훑을 필요 없이, 힙이 항상 가장 큰 값을 O(log m)에 꺼내주기 때문이다.

모든 작업량을 최대 힙(PriorityQueue, 역순 정렬)에 넣는다
n시간이 남아있고 힙이 비어있지 않은 동안, 가장 큰 값을 꺼내 1을 줄이고 0보다 크면 다시 넣는다
n을 다 쓰고 나면 힙에 남은 값들의 제곱을 모두 더해 반환한다

최종 코드

java

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // 항상 가장 큰 작업량을 꺼내는 최대 힙
        for(int work : works)
            pq.add(work);
        
        while(n > 0 && !pq.isEmpty()){
            int now = pq.poll();
            
            now--;
            n--;
            
            if(now > 0)
                pq.add(now);
        }
        
        // 시간이 남지 않은 뒤에도 남아있는 작업량들의 제곱 합이 피로도
        while(!pq.isEmpty()){
            answer+= Math.pow(pq.poll(), 2);
        }
        
        return answer;
    }
}

야근 지수

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기