[level3] 야근지수 JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

 

* 내가 생각한 방법 제일 높은 수를 계속 -1 해주기.

   즉, int 배열에 넣고, Arrays.sort(배열)를 사용해 정렬해 준 다음 배열의 마지막 자리를 -1 해주는 것이다.

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        
        int idx = works.length-1; 
        
        while(n > 0){
            Arrays.sort(works);
            works[idx] -= 1;
            n--;
        }
        
        for(int i = 0; i < works.length; i++){
            int tmp = works[i];
            if(tmp > 0){
                answer += (long)(tmp * tmp);
            }
        }
        return answer;
    }
}

답은 맞지만, 계속 재배열을 해주는 부분에서 효율성이 떨어진 듯.

 

이때 우리는 PriorityQueue<Integer>을 사용하면 된다!

큐는 선입선출이 기본이지만 우선순위큐를 사용하면 자동을 오름차순(내림차순)을 해준다. 

우선순위 큐를 내림차순으로 사용하기 위해선 아래와 같이 코드를 작성하면 된다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

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 : works) pq.add(i);
        
        for(int i = 0; i < n; i++){
            int tmp = pq.poll();
            if(tmp <= 0) break;
            pq.add(tmp-1);
        }
        
        while(!pq.isEmpty()){
            answer += Math.pow(pq.poll(), 2);
        }
        return answer;
    }
}