Today I Learned

오늘도 랜덤한 프로그래머스 lv.3짜리 문제를 풀어보았다.

야근지수

문제

야근피로도는 야근 시작 시점에서 남은 일의 작업량을 제곱해서 더한 값이다. N시간동안 야근 피로도를 최소화 하도록 일하려한다. 1시간동안 작업량 1만큼 처리할 때, 퇴근까지 남은 N시간과 각 일에대한 작업량 works에 대해 야근 피로도를 최소화한 값을 return해라.

풀이 과정

1. 문제에서 주어진 조건을 만족하려면 works에 주어진 수들을 하향 평준화 해야한다. 각각의 제곱이 합이 최소화 되야 하기 때문에 결국 수 자체를 낮춰야하는 것이다. 즉, 가장 높은수부터 차츰 깎아야한다.

2. 일단 주어진 시간 내에 다 처리할 수 있는 일이면 답이 0이므로 먼저 이 조건을 만족하게 return을 해둔다.

3. 우선순위큐를 최대힙으로 만들어 works에서 최대값만 나오도록 설정한다. intStream을 사용해 Comparator.reverseOrder()로 역정렬시켜 최대힙으로 만든다.

4. n시간동안 진행하므로 n번짜리 for문을 만든다. 그 안에서 최대힙에서 꺼낸 값을 1씩 차감시켜 다시 최대힙에 넣는 구조를 만든다.

5. for문이 다 진행되고 나면 남은 값들을 제곱으로 더해 답을 return한다.

Java 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
    
    int sum = 0;
    for (int work : works) {
      sum += work;
    }
    if (n>=sum) return 0;

    PriorityQueue<Integer> pq = IntStream.of(works)
        .boxed()
        .collect(Collectors.toCollection(() -> new PriorityQueue<Integer>(Comparator.reverseOrder())));

    for (int i = 0; i < n; i++) {
      Integer a = pq.poll();
      pq.offer(a-1);
    }

    long answer = 0;
    for (Integer c : pq) {
      answer += c*c;
    }
    return answer;

    }
}