[프로그래머스] 자바 LV3. 야근 지수

😖 실패한 풀이 

import java.util.*;

class Solution {
    public int findMaxIndex(int[] works){
        int max_index = 0;
        int max_num = 0;
        
        for(int i=0;i<works.length;i++){
            if(works[i] > max_num){
                max_num = works[i];
                max_index = i;
            }
        }
        return max_index;
    }
    
    public long getAnswer(int[] works){
        long answer = 0;
        
        for(int i=0;i<works.length;i++){
            long num = works[i];
            answer += (num*num);
        }
        return answer;
    }
    
    public long solution(int n, int[] works) {
        if(Arrays.stream(works).sum() <= n){
            return 0;
        }
        
        for(int i=0;i<n;i++){
            int max_index = findMaxIndex(works);
            works[max_index] -=1;
        }
        return getAnswer(works);
    }
}

 

접근한 방식은

1. 야근까지 남은 시간동안

2. 가장 많은 작업량을 요구하는 일을 찾고

3. 해당 일을 처리

하는 것이었다.

 

이렇게 하니 모든 테스트케이스를 통과했지만, 효율성에서 실패가 떴다.

 

두번째로 시도한 방법은 가장 큰 값에서 두번째로 큰 값만큼 계속해서 빼기..!

import java.util.*;

class Solution {
    public long getAnswer(int[] works){
        long answer = 0;
        
        for(int i=0;i<works.length;i++){
            answer += Math.pow(works[i], 2);
        }
        return answer;
    }
    
    public long solution(int n, int[] works) {
        int l = works.length;
        
        while(n>0){
            Arrays.sort(works);
            int diff = works[l-1]-works[l-2];
            if(works[l-1]<=0){
                return 0;
            }
            if(diff == 0){
                diff = 1;
            }
            
            if(diff > n){
                diff = n;
            }
            n -= diff;
            
            works[l-1] -= diff;
        }
        
        return getAnswer(works);
    }
}

 

그러나 이 코드도 계속해서 효율성 면에서 실패가 떴다..

결국에는 다른 풀이를 참고해서 해결했다. 

 

😖 실패 원인 분석

실패했던 이유는 정렬에서 비효율이 나기 때문이었던 것 같다.

매번 정렬을 해주는 부분에서 시간 초과가 난 것 같고, 이를 개선하기 위해서 다른 분들은 우선순위 큐를 사용하신 것을 확인했다.

 

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {

    public long solution(int n, int[] works) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i=0;i<works.length;i++){
            heap.add(works[i]);
        }
        
        for(int i=0;i<n;i++){
            int num = heap.poll();
            heap.add(num-1);
        }
        
        if(heap.peek()<=0){
            return 0;
        }
        
        long answer = 0;
        while(!heap.isEmpty()){
            int num = heap.poll();
            answer += (num*num);
        }
        return answer;
    }
}

 

😖 배운점

정렬을 효율적으로 하려면 최대 / 최소 heap 을 사용하자~!