[프로그래머스] Lv3. 야근 지수

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

프로그래머스

 

1차풀이

DFS로 빼줄 조합을 찾아서 완전탐색(무식하게 풀었다.) 

 

2차풀이

야근 지수를 낮추려면 주어진 수 사이의 편차를 최대한 줄이면 된다.

주어진 배열의 최댓값을 1개씩 줄여나가면 된다.

 

최댓값 추출에 O(logN)이 드는 우선순위 큐를 사용하였다.

 

 

1차 풀이 (33.3% 정답)

import java.util.*;

class Solution {
    
    long answer;
    
    public long solution(int n, int[] works) {
        // 피로도 최소화
        // 어떠한 것을 빼야 최소가 나올까?
        
        // 1. 완전 탐색
        // 2. 이분 탐색
        
        answer = 999999999;
        
        dfs(0, new int[n], n, works.length, works);
        
        System.out.println(answer);
        
        return answer == 999999999 ? 0 : answer;
    }
    
    public void dfs(int depth, int[] value, int n, int work, int[] works){
        if(depth == n) {
            // 최솟값 찾기
            findAnswer(value, works);
            return;
        }
        
        for(int i = 0; i < work; i++) { // 완전 탐색으로 지울 걸 찾는다.
            value[depth] = i;
            dfs(depth + 1, value, n, work, works);
        }
    }
    
    public void findAnswer(int[] values, int[] works) {
        long tmp = 0;
        
        int[] tmpWork = works.clone();
        
        for(int i = 0; i < values.length; i++){
            tmpWork[values[i]]--;
        }
        
        for(int value: tmpWork) {
            if(value <= 0) {
                continue;
            }
            tmp += Math.pow(value,2);
        }
        
        answer = Math.min(tmp, answer);
    }
}

 

2차 풀이

import java.util.*;

class Solution {

    
    public long solution(int n, int[] works) {
        
        long answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int work: works) {
            pq.offer(work);
        }
        
        // 우선 순위 큐? 제일 큰 값을 줄여나가면 된다.
        // 최댓값을 추출해서 1을 제거해준다.
        while(n>0) {
            int value = pq.poll();
            pq.offer(value > 0 ? value - 1 : value);
            
            n--;
        }
        
        for(int value: pq) {
            if(value == 0) {
                continue;
            }
            answer += Math.pow(value,2);
        }
        
        return answer;
    }
}

 

결과