[프로그래머스 코딩테스트] 야근 지수(Java)

  문제 설명

  회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근의 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근의 피로도를 최소화하도록 일할 겁니다. Demi가 1시간 동안 작업량 1만큼 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

 

  제한사항

• works는 길이 1이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

 

  입출력 예

works	n	result
[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1, 1]	3	0

import java.util.PriorityQueue;
import java.util.Collections;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        int sum = 0;
        for (int i: works) {
            sum += i;
        }
        if (sum <= n) {
            return answer;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i: works) {
            pq.add(i);
        }
        while (n > 0) {
            int max = pq.poll();
            pq.add(max - 1);
            n--;
        }
        while (!pq.isEmpty()) {
            int poll = pq.poll();
            answer += (long)Math.pow(poll, 2);
        }
        return answer;
    }
}

  변수 sum을 생성합니다.

  for-each문이 works를 순회합니다. 변수 i가 원소를 하나씩 받아 sum에 더하기 할당하여 works 배열의 원소의 총합을 구합니다.

  if문에서 sum이 n보다 작거나 같다면 야근 전에 일을 다 끝낼 수 있다는 뜻이므로 바로 answer를 반환합니다.

  야근을 해야하는 상황이라면 풀이는 다음과 같습니다.

  제네릭 타입으로 Integer를 갖는 PriorityQueue를 생성합니다. Collections 클래스의 reverseOrder 메소드를 이용하여 우선순위 큐가 내림차순으로 정렬될 수 있도록 합니다.

  for-each문이 works를 순회합니다. 변수 i가 원소를 하나씩 받아 우선순위 큐에 i를 삽입합니다.

  첫 번째 while문은 n이 0보다 큰 동안 반복합니다.

  변수 max를 생성하고, poll 메소드를 이용하여 우선순위 큐의 첫 번째 원소를 제거하고 제거한 값으로 변수를 초기화합니다.

  add 메소드를 이용하여 max에서 1 뺀 값을 다시 우선순위 큐에 삽입합니다.

  n이 감소하여 반복문의 반복 횟수가 차감됩니다.

  두 번째 while문은 isEmpty 메소드를 이용하여 우선순위 큐가 비어있지 않은 동안 반복합니다. 우선순위 큐의 원소를 하나씩 꺼내어 문제에서 제시한대로 계산할 차례입니다.

  변수 poll을 생성하고, poll 메소드를 이용하여 우선순위 큐의 첫 번째 원소를 제거하고 제거한 값으로 변수를 초기화합니다.

  answer에 Math 클래스의 pow 메소드를 이용하여 poll의 제곱값을 구하고, answer의 타입이 long이므로 long으로 캐스팅합니다.

 

  이렇게 풀이하는 이유는 결국 제곱된 값을 기준으로 결과가 산출되므로, 배열에서의 원소간 편차에 따라 값이 크게 달라지기 때문입니다. [1, 2, 3]과 [2, 2, 2]를 예시로 들어보겠습니다. 두 배열의 원소의 총합은 동일합니다.

1 * 1 + 2 * 2 + 3 * 3 = 1 + 4 + 9 = 14 2 * 2 + 2 * 2 + 2 * 2 = 4 + 4 + 4 = 12

  엄밀히 말하면 최댓값의 크기에 따라 큰 차이를 보인다고 할 수 있습니다. 따라서 이 풀이에서는 최댓값을 최대한 적게, 또 다른 원소간 편차가 적도록 우선순위 큐를 이용하여 1씩 줄여나가면서 배열의 모든 원소를 균등하게 만들어주는 것을 중점으로 하고 있습니다.

 

  헉 드디어 3단계 풀이에까지 돌입했네요. 아직 풀지 못한 이전 단계의 문제가 많지만 그럼에도 쾌거라고 생각하고 있습니다.