[프로그래머스][Level3][JAVA] 야근 지수

[문제 설명]

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

코딩테스트 연습 - 야근 지수

 

[풀이 내용]

야근 피로도(각 작업량 제곱의 합)이 최소가 되려면 가장 큰 수의 작업량부터 처리해야 한다. 

완전탐색으로 정답이 될 수 있는 모든 경우의 수를 나열해 보았는데 최소작업량이 더 작은 것보다 최대작업량이 더 작은것이 야근피로도가 더 적었다. 이유는 큰 수와 작은 수가 1차이가 나더라도 제곱의 차이는 확 커지기 때문이다. 

 

따라서 주어진 n만큼 순회하며 작업량이 담긴 배열중 가장 큰 작업량을 1씩 처리하고, 순회가 끝난 후 배열에 담긴 각 작업량의 제곱의 합을 구하면 된다. 

 

기억해두면 좋을 것은 다음 2가지 정도가 되겠다. 

1. 나열된 수들의 제곱의 합이 최소가 되려면 큰 수들을 작게 만들어 나가는 것이 최소값으로 가는 길이다. 

 

2. 배열을 매번 Arrays.sort 하여 최대값을 찾는 것보다 PriorityQueue 자료구조를 사용하는 방법이 더 효율성이 좋다. 

n번 순회할때마다 가장 큰 작업량을 구하려고 Arrays.sort 메소드로 최대값을 구했다. 

그런데 Arrays.sort 메소드는 비용이 비싸서 효율성 테스트에서 실패했다. PriorityQueue를 이용하여 max값을 바로 꺼내니 모든 테스트에서 통과할 수 있었다. 

 

[JAVA code]

package com.algorithm.programmers.level3;

import java.util.Collections;
import java.util.PriorityQueue;

public class Test11 {
    public static void main(String[] args) {

        int n = 3;
        int[] works =
                //{7, 5, 4, 3, 3};
                // {2, 1, 2};
                {1, 1};

        System.out.println("answer=" + solution(n, works));
    }

    public static long solution(int n, int[] works) {
        long answer = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // max heap 

        // PriorityQueue에 배열을 모두 담아 자동 정렬 
        for (int i = 0; i < works.length; i++) {
            pq.add(works[i]);
        }

        for (int i = 1; i <= n; i++) {
            int max = pq.poll();
            pq.add(max - 1);
        }

        while (!pq.isEmpty()) {
            int num = pq.poll();
            if (num > 0) {
                answer += Math.pow(num, 2);
            }
        }

        return answer;
    }
}