야근 지수

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

문제설명

• 주어진 파라미터: 퇴근까지 남은 시간 int n, 각 일에 대한 작업량 int[] works
• 반환값: long
• 야근 → 야근 피로도
• 야근 피로도 = 남은일의 제곱들의 합
• N 시간동안 야근 피로도 최소화하도록 일함
• 1시간 작업량 1
• 야근 피로도 최소화 값을 리턴하는 함수

풀이방식

1. 제곱들의 합을 최소한으로 하려면 → 큰수를 깍아야한다.(최대한 비슷한 크기로)
2. 줄일 수 있는 수는 n
3. 제곱들의 합을 return
4. 길이 1~20000(2 * 10^4) 1번 반복은 가능
5. 옆이랑 비슷하면 된다 → index 기준 잡고 n이 소진될때까지 반복하기
6. sort해서 큰수끼리만 비교 → 시간초과에 걸린다
7. 큰수에서 1만 계속 빼기 → PriorityQueue 활용

코드

풀이방식1

매번 정렬을 진행하고 가장 큰수에서 1을 빼주기

import java.util.*;

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

⇒ 효율성 테스트에서 탈락

→ 매번 정렬을 하는 부분에서 시간을 많이 잡아먹게 된다.

→ PriorityQueue로 가장 큰 수만 뽑을 수 있다면?

풀이방식2

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        long answer = 0;
        
        // 1. pq에 원소 넣기 
        for(int i : works){
            pq.offer(i);
        }
        
        // 2. n만큼 가장 큰 값을 빼주기 
        while(n > 0 && pq.size() != 0){
            int num = pq.poll();
            
            if(num == 0) break;
            
            num -= 1;
            n -= 1;
            
            pq.offer(num);
        }
        
        // 3. 하나씩 뽑으면서 answer에 더하기 
        while(pq.size() != 0){
            int num = pq.poll();
            answer += num * num;
        }
        
        return answer;
    }
}

회고

가장 처음 생각은 인접한 두 수를 계속 비교해가며 n을 소진시키는 것이었는데, 생각해보니 오류가 나는 부분이 많았다.
인접한 두 수의 차이가 커 n을 모두 소진시켰더니 그 다음수가 많이 큰 수라면 에러가 난다 → 큰 수를 모두 1씩 빼주는게 제곱의 합을 줄이는 방법이기 때문이다.

여러번 고민끝에 푼 문제라 뿌듯했다!

---

참 어렵주잉~?