프로그래머스, 야근 지수

문제 설명

Demi는 야근을 하면 야근 피로도가 쌓인다. 야근 피로도는 남은 작업시간 제곱의 합이며 1시간 야근을 하면 작업량을 1만큼 처리할 수 있다. 이때 야근 피로도는 남은 야근 작업량의 제곱의 합이다.  n을 모두 사용할 때 최소의 야근 작업량을 구하시오.

https://school.programmers.co.kr/learn/courses/30/lessons/12927?language=java 

프로그래머스

문제 풀이

첫 번째 접근

첫 번째 예를 한 번 보자. n이 4이고 작업량이 [4, 3, 3]일 때 야근을 하고 난 결과는 [2, 2, 2]이다. 또 두 번째 예를 보면 [2, 1, 2]에서 야근을 하고 나면 [1, 1, 2]가 된다.

 

최초 값과 그 결과를 비교하면 작업량이 큰 수대로 빠지는 것을 알 수 있다. 그러므로 우선순위 큐를 이용해서 제일 큰 숫자가 먼저 나오도록 하면 원하는 결과를 얻을 수 있다.

 

일단 우선순위 큐를 내림차순으로 선언하고 넣어준다.

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

for(int i=0; i<works.length; i++){
	pq.add(works[i]);
}

그리고 while문을 돌려주면서 제일 큰 수에 하나 빼주고 n 또한 하나 빼준다. 그리고 큐에서 빼준 수를 다시 넣어줘야 하는데, 만일 그 수가 0이라면 넣지 않는다.

 

여기서 탈출문은 우선순위 큐가 0이거나 n이 0일 때다.

        while(true){
            
            if(pq.size() == 0 || n == 0){
                break;
            }

            int current = pq.poll();
            current--;
            n--;
            if(current == 0){
                continue;
            }
            pq.add(current);
        }

우선순위 큐가 0이면 0을 반환한다. 0이 아니면 숫자를 큐에서 하나씩 빼서 제곱을 한 후 answer에 더해준다.

        if(pq.size() == 0){
            return 0;
        }
        
        while(pq.size() != 0){
            answer += (Math.pow(pq.poll(), 2));
        }

코드

java

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i=0; i<works.length; i++){
            pq.add(works[i]);
        }
        
        while(true){
            
            if(pq.size() == 0 || n == 0){
                break;
            }

            int current = pq.poll();
            current--;
            n--;
            if(current == 0){
                continue;
            }
            pq.add(current);
        }
        
        if(pq.size() == 0){
            return 0;
        }
        
        while(pq.size() != 0){
            answer += (Math.pow(pq.poll(), 2));
        }
        
        return answer;
    }
}