[programmers] 야근 지수 - Java

야근 지수

문제 설명

제한 사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.

• works의 원소는 50000 이하인 자연수입니다.

• n은 1,000,000 이하인 자연수입니다.

입출력 예

입출력 예 설명

처음 시도한 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        for(int i=n; i>0; i--){
            Arrays.sort(works);
            if(works[works.length-1]>0){
                works[works.length-1]--;
            }
        }
        for(int i=0; i<works.length; i++){
            answer += Math.pow(works[i], 2);
        }
            
        return answer;
    }
}

개선한 코드

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

class Solution {
    public long solution(int n, int[] works) {
        PriorityQueue<Integer> overtime = new PriorityQueue<>(Collections.reverseOrder());

        for (int work : works) {
            overtime.offer(work);
        }
        
        for (int i = 0; i < n; i++) {
            int max = (int)overtime.poll();
            if (max <= 0) break;
            overtime.offer(max - 1);
        }
        
        return sumPow(overtime);
    }
    
    long sumPow(PriorityQueue<Integer> works) {
        long sum = 0;
        while (!works.isEmpty()) {
            sum += Math.pow(works.poll(), 2);
        }
        return sum;
    }
    
}

핵심 키워드

• 처음 시도한 코드는 n만큼 반복할 때마다 배열을 정렬해서 배열의 최댓값에서 1을 빼는 방식으로 접근했다.
• 이 경우 시간 복잡도는 O(nlogn)이고, 효율성 테스트를 통과하지 못했다.

• 이를 해결하기 위해 우선순위 큐를 사용해서 작업량을 내림차순으로 정렬해서 저장했다.
• 주어진 배열을 순회하면서 각 작업량을 우선순위 큐에 저장하고, n만큼 반복문을 수행한다.
• 우선순위 큐에서 가장 많은 작업량을 가져오고 max 변수에 저장한다.
• 만약 max가 0 이하라면 더 이상 작업을 할 수 없으므로 반복을 종료한다.
• 작업을 할 수 있다면 max에서 1을 빼고 다시 우선순위 큐에 넣어준다.
• 그 후 우선순위 큐에 있는 값들의 제곱의 합을 반환한다.

결론!