맨처음에는 arryalist의 Collections.max()와 arr.indexOf()를 사용했지만 시간 초과가 떠서 PriorityQueue를 사용했다.
가장 제곱의 합이 적게 나오려면 가장 큰수가 작아야한다.
ex) 9 1 1 보다 5 4 2 가 더 작다. 그래서 가장 큰 수를 제일 줄여나가야 한다.
그래서 내림차순으로 정렬되는 PriorityQueue를 선언했다.PriorityQueue<Integer> pq = new PriorityQueue(Collections.reverseOrder());
그리고 n이 0이되거나, pq에서 제일큰값 pq.peek()이 0이될때까지 반복되는 반복문을 돌게 한다.
반복문을 돌면서 pq의 가장큰값 pq.poll()에 -1한값을 다시 pq에 넣었다.
이렇게 되면 pq의 원소들의 숫자는 그대로 유지가 되면서 계속 내림차순으로 정렬되기 때문.while(n>0 && pq.peek()!=0){ pq.add(pq.poll()-1); n--; }
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(n>0 && pq.peek()!=0){
pq.add(pq.poll()-1);
n--;
}
while(!pq.isEmpty()){
int num = pq.poll();
answer+=num*num;
}
return answer;
}
}