Programmers - 야근 지수 with JAVA

 

 

문제

일할 수 있는 양 N, 일마다 남은 양 리스트가 주어질 때 (ex [2, 3, 4]) N만큼 일하고 남은 일리스트의 값들의 제곱의 합의 최소를 구하라.

 

 

 

로직

이 문제는 우선순위 큐로 해결하면 쉽다. 하지만 이 아이디어가 떠오르질 않았어서 기록을 해두고자 한다.

 

1. 모든 남은 일의 양을 우선순위 큐에 넣는다(최대값 우선순위 큐)

2. 하나씩 값을 꺼내서 1을 빼고 다시 큐에 넣고 할 수 있는 일의 양 N에서도 1을 뺀다.

2-1. 만약 꺼낸 값(최대 값)이 0이라면 모든 일을 다 처리한 것이므로 종료한다.

2-2. 만약 N이 0이라면 더이상 일을 할 수 없으므로 종료한다.

 

 

 

코드

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        PriorityQueue<Integer> queue 
            = new PriorityQueue<>(Comparator.comparing(arr -> -arr));
        for(int work : works){
            queue.add(work);
        }
        while(true){
            int max_value = queue.poll();
            if(max_value == 0){
                return 0;
            }
            max_value -= 1;
            n -= 1;
            queue.add(max_value);
            if(n == 0){
                break;
            }
        }
        for(int i : queue){
            answer += i*i;
        }
        return answer;
    }
}

 

 

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        PriorityQueue<Integer> queue 
            = new PriorityQueue<>(Comparator.comparing(arr -> - arr));
        for(int work : works){
            queue.add(work);
        }
        for(int i=0; i<n; i++){
            queue.add(queue.poll()-1);
        }
       	for(int i : queue){
            if(i <= 0){
                continue;
            }
            answer += i*i;
        }
        return answer;
    }
}