[프로그래머스] 야근지수 - JAVA

문제링크 🚩

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

프로그래머스

 

​

📕 문제 접근 📕

잘 못 된 접근 :

// 모든 수를 낮게 만드는게 이득인가?
// 7 -> 1 3 3 -> 18
//  2, 2, 3 -> 4 + 4 + 9 => 17
//  모든 수를 가장 낮게 만드는게 이득 
//  배열을 순회하기에는 시간이 부족함
//  그럼 어떤 방법으러 해결해야하는가?
//  전부다 더하고 n을 빼고 수를 나눈다면?

=> 문제 발생

그럼 2, 1, 2 에 n이 1 인경우 4가 되고 2,2 로 분열하여 1, 1, 2 보다 큰 값이 나옴 

 

잘 된 접근 

PriorityQueue로 내림차순 정렬 후

n이 0이 될 때까지 가장 큰 값에서 1을 빼서 연산하기 

 

 

💻 Code 💻

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

class Solution {
    public long solution(int n, int[] works) {
        PriorityQueue<Integer> overtime = new PriorityQueue<>(Collections.reverseOrder());

        for (int work : works) {
            overtime.offer(work);
        }
        
        for (int i = 0; i < n; i++) {
            int max = (int)overtime.poll();
            if (max <= 0) break;
            overtime.offer(max - 1);
        }
        
        return sumPow(overtime);
    }
    
    long sumPow(PriorityQueue<Integer> works) {
        long sum = 0;
        while (!works.isEmpty()) {
            sum += Math.pow(works.poll(), 2);
        }
        return sum;
    }
}

 

📖 배운점 📖

그리디하게 접근 하는 것이 안좋다는 것을 크게 느꼈다.

효율적인 풀이를 생각해야하는데 너무 그리디 적으로 접근하고 있는 것 같다.