[프로그래머스 Level.3] 야근 지수 (연습문제) (Java)

문제 링크

https://school.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 이하인 자연수입니다.

 

 

입출력 예

works	n	result
[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1,1]	3	0

 

 

입출력 예 설명

 

 

입출력 예 #1

n=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 4시간동안 일을 한 결과는 [2, 2, 2]입니다. 이 때 야근 지수는 22 + 22 + 22 = 12 입니다.

 

 

 

입출력 예 #2

n=1일 때, 남은 일의 작업량이 [2,1,2]라면 야근 지수를 최소화하기 위해 1시간동안 일을 한 결과는 [1,1,2]입니다. 야근지수는 12 + 12 + 22 = 6입니다.

 

 

 

입출력 예 #3

 

남은 작업량이 없으므로 피로도는 0입니다.

 

 

 

 

나의 코드

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.offer(works[i]);
        }
        
        while(n > 0) {
            int work = pq.poll();
            if(work <= 0) break;
            work--;
            pq.offer(work);
            n--;
        }
        
        for(int work : pq) {
            answer += work * work;
        }
        
        return answer;
    }
}

 

풀이

1. 야근 피로도는 works의 원소들을 제곱하여 더하는 것이므로 야근 피로도가 최소가 되려면 works의 원소들이 가장 차이가 안나도록 줄어들어야 한다.
   예를 들어 works가 {4, 3, 3} 일 때 n이 4라면 {2, 2, 2}가 되어야 하고 works가 {4, 3, 3} 일 때 n이 7이라면 {1, 1, 2}가 되어야 한다.
2. 내림차순 정렬하는 우선순위큐를 생성하고 works를 우선순위큐에 담는다. 따라서 works의 원소가 가장 큰 수가 우선순위큐의 제일 앞에 위치한다.
3. n만큼 for문을 돌면서 우선순위큐가 비어있지 않다면 우선순위큐의 첫 데이터를 꺼내서 -1을 한 뒤에 0보다 크다면 -1한 데이터를 다시 우선순위큐에 담는다.
4. for문을 다 돌고 난 뒤 우선순위큐가 비어있다면 0을 리턴하고 아니라면 우선순위큐가 빌 때까지 데이터를 꺼내서 Math.pow()를 이용하여 제곱한 뒤 answer에 더해주는 것을 반복한 후 answer를 반환한다.