[프로그래머스] 야근 지수 (java) Dynamic_programming
2020-03-24
야근 지수 (프로그래머스> Dynamic_programming)
문제설명
회사원 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
풀이
package Dynamic_programming;
import java.util.*;
public class prog_3_야근지수 {
//1h
static public long solution(int n, int[] works) {
long answer = 0;
PriorityQueue<Integer> qu = new PriorityQueue<>(); // min heap
//PriorityQueue<Integer> max_heap = new PriorityQueue<>(Collections.reverseOrder()); ->max heap 만드는 법
int len = 0;
for(int i=0;i<works.length; i++) {
len += works[i];
qu.add(-1 * works[i]); //min힙이니까 -1 곱해줘서 풀어주고
}
if(len <= n)
return 0;
else {
while(n>0) {
int max = qu.poll();
System.out.println(max);
qu.add(max+1); //-를 곱해놨으니까 +1해줘야 빼지는 개념
n--;
}
}
int size = qu.size();
for(int i=0;i<size; i++) {
answer += Math.pow(-1 * qu.poll(), 2); // -1해줬던걸 다시 +로 바꿔준뒤 제곱해준다
}
return answer;
}
public static void main(String[] args) {
int w[] = {4,3,3};
System.out.println(solution(4,w));
}
}
후기 (1h)
하루가 지날 때마다 제일 큰값을 하나씩 빼준다는 개념을 빠르게 파악할 수 있다면, n–될 때마다 최대값을 찾아 빼주면 됐다.
- 하지만 일반 리스트에 sort함수를 매번 사용하면 시간초과가 뜨기 때문에
- 검색에 속도가 빠른 PriorityQueue를 사용했다
- PriorityQueue는 default가 minheap으로 되어있기때문에, poll()할때마다 제일 작은 값이 빠져서 이를 해결하기위해 모든 값에 -1을 곱해주었다
- -1을 곱해준 값들에는 +1을 해주어 빼는 연산을 해주었고
- 나중에 나온 값의 제곱을 더해 문제를 해결했다
정말 하나씩 빼줘야 한다는 생각은 했는데, 너무 수학적인 문제들이 많다…
그리고 검색이 오래걸릴때는 pq를 사용해준다는 것, 초기화할 때 reverseOrder()를 사용하면 maxheap으로 사용할 수 있다.
