[12927] 야근 지수

✔ 야근 지수

[프로그래머스 12927]

문제 분석하기

야근 피로도는 각 작업량의 제곱의 합이므로

각 작업량 중 가장 큰 값의 작업을 줄여주어 전체적으로 제곱의 합을 적어지게 해야 함

그러므로 우선순위 큐를 사용해 가장 많은 작업량을 찾아 작업량만큼 반복하며 줄여주고 남은 작업량의 제곱의 합을 더해줌

손으로 풀어보기

1. 우선순위 큐를 사용해 가장 많은 작업량을 찾아 작업량만큼 반복하며 야근
2. 남은 작업량의 제곱의 합을 구해 반환

슈도코드 작성하기

works(작업량)
n(퇴근까지 남은 시간)
answer(야근 피로도를 최소화한 값)
worksQueue(작업량을 담을 최대값 우선순위 큐)
worksQueue에 works 저장
for(i -> n만큼) {
    maxWork(worksQueue에서 가장 큰 작업량)
    if(maxWork가 0보다 작거나 같다면)
        모든 작업을 끝냈으므로 break
    maxWork를 -1만큼 줄여서 다시 저장
}
while(worksQueue가 비지 않는 동안) {
    answer에 작업량을 제곱한 값을 더하여 갱신
}
answer 반환

코드 구현하기

/**
 * 12927) 야근_지수
 */
public class L010_12927 {
    // n(퇴근까지 남은 시간)
    // works(작업량)
    public long solution(int n, int[] works) {
        // answer(야근 피로도를 최소화한 값)
        long answer = 0;
        // worksQueue(작업량을 담을 최대값 우선순위 큐)
        PriorityQueue<Integer> worksQueue = new PriorityQueue<>(Collections.reverseOrder());
        // worksQueue에 works 저장
        for (int work : works) {
            worksQueue.offer(work);
        }
        for (int i = 0; i < n; i++) {
            // maxWork(worksQueue에서 가장 큰 작업량)
            int maxWork = worksQueue.poll();
            // maxWork가 0보다 작거나 같다면
            if (maxWork <= 0)
                // 모든 작업을 끝냈으므로 break
                break;
            // maxWork를 -1만큼 줄여서 다시 저장
            worksQueue.offer(maxWork - 1);
        }
        // worksQueue가 비지 않는 동안
        while (!worksQueue.isEmpty()) {
            // answer에 작업량을 제곱한 값을 더하여 갱신
            answer += Math.pow(worksQueue.poll(), 2);
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L010_12927 solution = new L010_12927();

        int n = 4;
        int[] works = { 4, 3, 3 };

        long result = solution.solution(n, works);

        System.out.println(result);
    }
}