프로그래머스 야근지수 (C#) [Lv. 3]

프로그래머스

 

야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다.

Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다

Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때,

퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해

야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

 

ex) works = [4, 3, 3], k = 4

works를 [2, 2, 2]로 만들어야 최소 야근 피로도가 나옵니다.

 

풀이 방법

야근 피로도의 공식은 아래와 같습니다.

works[0] ^ works + works[1] * workds[1] .... works[N] * workds[N]

예시들을 계산해보면, 하나의 일감만 끝내는 것 보다 최대한 모든 일감의 크기를 같으면서 작게 하는게 중요하다는 것을 알 수 있습니다.

 

이것을 해결하기 위해서는 가장 큰 원소의 값을 1씩 내려주는 것을 k번 반복하면 됩니다.

하지만, 가장 큰 원소를 찾는 시간 * K번의 반복 회수에 의해 시간초과가 발생하게 됩니다.

 

이것을 해결하기 위해 우선순위큐를 사용합니다.

최신 C#버전 에서는 우선순위큐를 지원하기는 하지만, 프로그래머스에서는 사용할 수 없기 때문에 직접 구현해야합니다.

 

 

우선순위 큐

public class PriorityQueue
{
    public void Add(int value)
    {
        arr[size++] = value;
        
        int cur = size-1;
        
        while (cur > 0)
        {
            int parent = (cur - 1) / 2;
            
            if (arr[parent] < arr[cur])
            {
                int temp = arr[cur];
                arr[cur] = arr[parent];
                arr[parent] = temp;
                
                cur = parent;
            }
            else
                break;
        }
    }
    

    
    public int Pop()
    {
        int ret = arr[0];
        arr[0] = arr[--size];
        
        int cur = 0;
        
        while (cur < size-1)
        {
            int left = cur * 2 + 1;
            int right = left+1;
            
            if (left >= size)
                break;
            
            if (right < size && arr[right] > arr[left])
                left = right;
            
            if (arr[left] > arr[cur])
            {
                int temp = arr[left];
                arr[left] = arr[cur];
                arr[cur] = temp;
                
                cur = left;
            }
            else
                break;
        }
        
        return ret;
    }
    
    public bool IsEmpty() => size == 0;
    
    
    int size = 0;
    int[] arr = new int[30000];
}

 

 

정답 코드

using System;
using System.Collections.Generic;

public class Solution 
{
    
    public long solution(int n, int[] works) 
    {
        long answer = 0;
        PriorityQueue pq = new PriorityQueue();

        foreach (int work in works)
            pq.Add(work);
            
        while (n-- > 0 && !pq.IsEmpty())
        {
            int cur = pq.Pop();
            if (cur == 0)
                continue;
            
            pq.Add(cur-1); 
        }
        
        while (!pq.IsEmpty())
        {
            int value = pq.Pop();
            answer += (long)value * (long)value;
        }
        
        return answer;
    }
}