문제 설명
Demi가 n시간 동안 야근 피로도를 최소화한 값을 반환하는 문제이다.
여기서 야근 피로도는 남은 작업시간의 제곱을 전부 더한 값이다.
https://school.programmers.co.kr/learn/courses/30/lessons/12927?language=java#
문제 풀이
첫 번째 접근
일단 제곱을 해서 모두 더한 값이 제일 작게 만들기 위해서는 제곱하기 전의 값이 작아야 한다고 생각했다. n에 있는 횟수만큼 숫자를 빼줘야 하기 때문에 먼저 배열을 내림차순으로 정렬한 후 뒤에 있는 숫자보다 작을 때까지 빼주고 다음 숫자로 넘어가는 것이다.
이렇게 푸니까 주어진 예시는 전부 통과했다.
그.러.나.
실전 테스트 케이스를 돌리니 전부 틀리게 나오는 거 아닌가? 그래서 다시금 생각해 봤더니 내가 한 풀이는 n에 숫자가 남아 있어도 딱 1번만 배열을 돌리기 때문에 남은 n을 전부 털어내지 못하는 것이다.
그래서 n이 0이 될 때까지 계속 돌려줘야 하는데... 이걸 어떻게 하나? 싶었던 참에 다른 사람의 풀이를 참고하니 우선 순위 큐를 써야 한다는 것을 알았다.
두 번째 접근
우선순위 큐 중 큰 값을 우선순위로 두는 큐를 쓴다면 굳이 정렬을 할 필요가 없다. 뿐만 아니라 계산하고 난 값을 큐에서 빼고 뒤로 다시 넣을 수도 있어 반복문을 복잡하게 만들 필요도 없다.
그렇다면 해결되는 거 아닌가? 싶었으나... 나는 여전히 제일 큰 값을 두 번째로 큰 값보다 더 작게 만들어 줘야 한다고 생각했다.
첫 번째 값이 10이고 두 번째 값이 7이면 첫 번째 값을 6으로 만든 다음에 n에다가 4를 빼주고... 만일 n이 4보다 작으면... 어쩌고 저쩌고... 이렇게 하다보니 너무 복잡해지고 문제를 정확하게 풀지도 못했다.
세 번째 접근
결국 다른 사람들의 풀이를 봤는데, 내가 생각한 아이디어는 비슷하지만 더 간단하게 풀 수 있는 문제였다. n이 0보다 클 때까지 큐에 값을 빼서 n에 1을 빼주고 큐에서 가져온 값에 1을 빼줘서 큐에 넣는 방식이다. 이때 해당 큐는 우선순위 큐이기 때문에 빠진 숫자가 무조건 큐에서 제일 큰 숫자이다. 그러므로 만일 큐에서 가져온 값이 0보다 작거나 같으면 이는 더이상 뺄 값이 없기 때문에 break로 탈출하면 된다.
그리고 큐에 있는 값들을 전부 빼서 2제곱 하면 된다. 0의 제곱은 0이기에 굳이 신경쓸 필요 없다.
코드
java
import java.util.*;
class Solution {
public long solution(int n, int[] works) {
long answer = 0;
Integer[] works2 = new Integer[works.length];
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for(int i=0; i<works.length; i++){
pq.add(works[i]);
}
while(n > 0){
int current = pq.poll();
if(current <= 0){
break;
}
n--;
pq.offer(current - 1);
}
while(!pq.isEmpty()){
answer += Math.pow(pq.poll(), 2);
}
return answer;
}
}