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

프로그래머스

연습문제

 

프로그래머스

야근 지수

 

문제 정리

1.회사원 Demi는 가끔 야근을 하지만, 야근을 하면 야근 피로도가 생긴다.
2. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량의 제곱만큼 생긴다.
3. 1시간 동안 작업량 1만큼 처리할 수 있다.
4. 퇴근까지 남은 n시간과 각 일에 대한 작업량 works 배열이 주어진다.
5. 여기서 피로도가 최소화된 값을 return 하기

 

 

시작하기 전 접근 방법

1. 작업량이 무작위로 되어 있는 works배열을 값이 큰 것부터 정렬을 한다.
2. 값이 가장 큰 수만 줄인다면 최소값이 나올 수 없다.
2.1 ex) n=4이고, [4,3,3]이 주워 졌을 때 4에 몰빵을 하면 [0,3,3]이 되지만 피로도는 9+9=18이 된다.
2.2 ex) 이 방법 말고 분배해서 균형있게 줄인다면 [2,2,2]일 때 4+4+4=12로 12가 된다.
3. 정렬을 하여 n=0이 될때까지 가장 works에서 가장 수를 1씩 줄이면서 계산한다.
4. list를 역정렬해서 할까 우선순위 큐를 사용하여 할까 고민하였다.
5. 우선순위 큐를 사용하는 것이 처음 정렬을 하고 queue에 값이 들어올 때 우선순위큐 때문에 정렬이 되기 떄문에 우선순위 큐를 이용하였다.

입출력 예

 

 

1. 우선순위큐를 선언하면 일반적으로 오름차순으로 정렬되기 때문에 내림차순으로 바꾸며 works배열에 있는 작업량을 큐에 추가한다.

PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder()); //내림차순
        for(int i=0; i<works.length; i++){
            q.offer(works[i]);
        }

 

 

2. 매개 값으로 주어진 n이 0이 될 때까지 우선순위큐에 있는 값 중에서 가장 큰 수를 1씩 줄이면서 반복한다.
3. 작업량이 더이상 줄어들 수 없다면 반목문을 멈추며 가장 큰 수를 1씩 줄이고 다시 que에 넣고 하는 과정을 반복한다.
4. 큐에 있는 값이 최종 균등하게 감소한 작업량이기 때문에 반복문을 통해 제곱하여 answer에 더하여 return값을 계산한다.

while(n!=0){
	int index = q.poll(); //가장 큰 수부터
	if(index==0) break;
	index--;
	q.offer(index);
	n--;
}
for(int time : q){
	answer += time*time;
}

 

 

전체 코드

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder()); //내림차순
        for(int i=0; i<works.length; i++){
            q.offer(works[i]);
        }

        while(n!=0){
            int index = q.poll(); //가장 큰 수부터
            if(index==0) break;
            index--;
            q.offer(index);
            n--;
        }
        long answer = 0;
        for(int time : q){
            answer += time*time;
        }
        return answer;
    }
}