PG12927 - 골3 - 그리디, 자료구조, 최적화

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        int sum = 0;
        // map 느낌으로
        int[] cnt = new int[50001];
        int max = -1;
        
        for(int w : works){
            max = Math.max(w, max);
            cnt[w]++;
            sum += w;
        }

        if(sum <= n)
            return 0;
        
        int curMax = max;
        while(n > 0 && curMax > 0){
            // pq 아니고 직접 idx 움직이는거라 비어있으면 내려야함
            if(cnt[curMax] == 0){
                curMax--;
                continue;
            }
            
            int cc = cnt[curMax];
            if(n >= cc){
                cnt[curMax] = 0;
                cnt[curMax-1] += cc;
                n -= cc;
                curMax = curMax-1;
            }
            else{
                cnt[curMax] = cc-n;
                cnt[curMax-1] += n;
                n = 0;
            }
        }
        
        
        long ans = 0;
        for(int i = 1; i <= curMax; i++){
            if(cnt[i] == 0)
                continue;
            ans += (long)i * i * cnt[i];
        }
        
        return ans;
    }
}

 

문제

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

 

풀이

일단 최대값을 최소화하는 문제로 생각함. 그러려면 평평하게 만들고 

처음에는 우선순위큐로 생각했는데 N이 최대 백만이라 nlog n으로 처리하면 시간초과가 터짐. 

 

입력 데이터에는 중복 데이터가 포함되고 데이터의 최대값 범위가 자연수이며 최대 50000이라 counting 배열로 하기로 함

-> counting map 느낌으로

 

그래서 count 배열 업데이트할때 max 정해주고 

max가 0 초과고 n이 0 초과일때 현재 max 값에서 그룹 단위로 제거해주고 max 값 업데이트 하고

만약 그룹 크기가 현재 n보다 클때 조건처리를 추가로 해줌

 

그리고 pq 방식은 매번 정렬로 max 값이 계산되어 나오지만 이건 인덱스로 직접 내려가는 방식이라 현재 Max 값의 count가 0이라면 -> 처리할 그룹이 존재하지 않는다면 invalid 한 값이므로 curMax --를 해줌

 

확장 : 만약 데이터 값 범위가 크다면?

distinct한 값의 종류를 K라 하면SortedMap의 구현체를 TreeMap으로 가져가고 그러면 값의 갯수를 n이라 하면 시간복잡도는 n log K가 됨. 그리고 curMax를 불러올때는 treeMap이 이미 key를 기준으로 정렬된 상태이기 때문에 map.lastKey()로 최대값 뽑아오면 됨.