[C#]프로그래머스/야근지수/우선순위큐

@오답코드
- 단순하게 DFS, 백트래킹으로 가능한 경우의 수를 검사했다.
기본 테스트 케이스는 모두 통과했지만, 일부 케이스에서 시간 초과가 발생했다.

public class Solution
{
    private int minValue = int.MaxValue;
    public long solution(int n, int[] works)
    {
        DFS(n, works);
        
        //남은 작업량이 없어서 최소값 갱신이 안된 경우의 예외처리
        return minValue == int.MaxValue ? 0 : minValue;
    }
 
    public void DFS(int workingHours, int[] works)
    {
        //다 일했으면 야근지수를 검사하고 최소값 갱신
        if (workingHours == 0)
        {
            int sum = works.Select(x => x * x).Sum();
 
            minValue = Math.Min(sum, minValue);
            return;
        }
 
        //1시간 일했다.
        workingHours--;
 
        for(int i = 0; i < works.Length; i++)
        {
            if (works[i] - 1 < 0)
                continue;
 
            works[i]--;
 
            //일한 시간을 뺀 works를 깊은 복사
            int[] newWorks = new int[works.Length];
            Array.Copy(works, newWorks, works.Length);
 
            DFS(workingHours, newWorks);
 
            //빼기 전 값으로 배열을 원복한다. (백트래킹)
            works[i]++;
        }
    }
}

@정답코드

-야근지수가 최소가 되려면, 작업량이 가장 많은 것부터 빼면 된다.

때문에 최대 우선순위큐를 구현해서 문제를 해결했고, 효율성 테스트를 통과했다.

using System.Collections.Generic;
 
public class PriorityQueue<T>
{
    private readonly List<T> heap;
 
    private readonly IComparer<T> comparer;
 
    public PriorityQueue(IComparer<T> comparerValue, int length)
    {
        heap = new List<T>(length);
        comparer = comparerValue;
    }
 
    public int Count => heap.Count;
 
    public void Enqueue(T item)
    {
        heap.Add(item);
        int index = Count - 1;
 
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
 
            if (comparer.Compare(heap[index], heap[parentIndex]) >= 0)
                break;
 
            Swap(index, parentIndex);
 
            index = parentIndex;
        }
    }
 
    public T Dequeue()
    {
        T item = heap[0];
 
        heap[0] = heap[Count - 1];
        heap.RemoveAt(Count - 1);
 
        int index = 0;
 
        while (true)
        {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
 
            if (leftChildIndex >= Count)
                break;
 
            int minChildIndex = (rightChildIndex < Count   
                && comparer.Compare(heap[rightChildIndex], heap[leftChildIndex]) < 0) ?    
                rightChildIndex : leftChildIndex;
 
            if (comparer.Compare(heap[index], heap[minChildIndex]) <= 0)
                break;
 
            Swap(index, minChildIndex);
 
            index = minChildIndex;
        }
 
        return item;
    }
 
    private void Swap(int indexA, int indexB)
    {
        T temp = heap[indexA];
        heap[indexA] = heap[indexB];
        heap[indexB] = temp;
    }
}
 
public class Solution
{
    public long solution(int n, int[] works)
    {
        //구현된 최소 우선 순위 큐를 Comparer를 새로 정의해서 최대 우선 순위 큐로 변경
        PriorityQueue<int> priorityQueue = new PriorityQueue<int>(Comparer<int>.Create((x, y) => y.CompareTo(x)), works.Length);
 
        //우선 순위 큐 삽입
        foreach (var work in works)
            priorityQueue.Enqueue(work);
 
        while (n > 0 && priorityQueue.Count > 0)
        {
            //가장 큰 작업을 뽑고 뺀다.
            int maxWork = priorityQueue.Dequeue();
 
            if (maxWork > 0)
            {
                maxWork--;
                n--;
                priorityQueue.Enqueue(maxWork);
            }
        }
 
        long sum = 0;
 
        while (priorityQueue.Count > 0)
        {
            //제곱 계산
            int dequeuedValue = priorityQueue.Dequeue();
            sum += (long)dequeuedValue * dequeuedValue;
        }
 
        return sum;
    }
}