[프로그래머스/3단계/자바] 야근 지수 (정확성 O, 효율성 O)

야근지수

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

코딩테스트 연습 - 야근 지수 | 프로그래머스

문제 설명

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

제한 사항

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

풀이1 (PriorityQueue)

---

야근은 없어져서 하는데... 회사원 Demi는 야근을 너무 자주해서, 야근 피로도까지 따로 계산을 하는군요.. ㅠㅠ

 

보통 다른 분들은 이 문제를 PriorityQueue로 정렬이 반대로 되게 선언해서,

n이 0이 될 때까지 가장 큰 값에서 1씩 빼는 식으로 많이 풀으셨더라고요.

코드1

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;
    }
    
}

---

풀이2 (일한 시간의 재분배)

저는 PriorityQueue을 정렬을 반대로 하는 것을 생각 못 해서, 아예 반대로 풀었었습니다.

회사원 Demi의 총 일한 시간에서 야근시간 n을 뺀 다음, 남은 시간을 다시 배분해주었는데요.

아무래도 위에 풀이1가 더 효율적인 풀이 같네요!

코드2

class Solution {
    public long solution(int n, int[] works) {
        int[] result = new int[works.length];
        int totalovertime = sumArr(works) - n;
        int time = totalovertime;
        
        if (time <= 0) return 0;

        for (int i=0; i<works.length; i++) {
            result[i] = (works[i] < totalovertime/works.length)? works[i] : totalovertime/works.length;
            time -= result[i];
        }
        
        for (int i=0; i<works.length; i++) {
            if (time <= 0) break;
            if (works[i] > result[i]) {
                result[i]++;
                time--;
            }
            if (i == works.length - 1) i = -1;
        }
       
        return getTiredness(result);
    }
    
    long getTiredness(int[] works) {
        long sum = 0;
        for (int work : works) {
            sum += work * work;
        }
        return sum;
    }
    
    int sumArr(int[] works) {
        int sum = 0;
        for (int work : works) {
            sum += work;
        }
        return sum;
    }
}

체점 결과