[Programmers] 야근 지수 - Java

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

프로그래머스

---

1. 문제

야근 피로도를 최소화하면 된다. 야근 피로도는 일을 처리하고 남은 일의 양 원소들을 각각 제곱해서 더한 값이다.

works 배열에 일의 양이 주어지고 1시간에 1만큼의 일을 한다고 할 때,

N시간 동안 일을 처리했을 때 야근 피로도의 최솟값을 출력한다.

 

2. 풀이

처음엔 수학으로 접근하였으나, 이렇게 되면 '최소한'의 야근 피로도를 구할 수 없다.

내림차순으로 원소를 모두 정렬하여 거기서 N시간 만큼을 빼주는 것이 가장 효율적으로 최솟값을 구할 수 있는 방법이라고 생각했다.

때문에 최소힙을 사용하기 위하여 우선순위큐를 reverse해서 사용했다. 

 

1. works 원소들을 하나하나 pq에 넣어준다.

2. 내림차순으로 정렬된 pq에서 맨 앞의 원소를 N만큼 반복해서 poll() 해준다.

3. poll한 값이 0보다 작을 경우, 최댓값이 0이란 의미이고 뒤에 남은 원소들 또한 모두 0보다 작거나 같다는 의미이므로

더 볼 것도 없이 바로 0을 return해준다.

4. 남아있는 원소값들에 대해 제곱하여 더한 후 return해준다.

 

3. 코드

import java.io.*;
import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<> ((o1,o2)->o2-o1);
        
        for (int work:works) {
            pq.offer(work);
        }
        
        for (int i=0; i<n; i++) {
            int num = pq.poll();
            if (num <= 0) {
                return 0;
            }
            pq.offer(num-1);
        }
        
        while (!pq.isEmpty()) {
            ans += Math.pow(pq.poll(), 2);
        }
        
        return ans;
    }
}

4. 사담

천천히 하나씩 쌓아 나가면 언젠간 반드시 도착해있을거라 믿는다.. 나도 실력이 많이 늘기를 바란다. 그럴려면 더 열심히해야지 잠을 왜 자 일어나