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

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/12927

 

 

나의 풀이

public long solution(int n, int[] works) 
{
    Array.Sort(works);

    for(int i = 0; i < n; ++i)
    {
        int maxIndex = works.Length - 1; // 맨 뒤에서 부터 탐색
        // 앞의 숫자가 같거나 크다면 index를 앞으로 옮긴다.
        while(maxIndex > 0 && works[maxIndex - 1] >= works[maxIndex])
            --maxIndex;

        if(works[maxIndex] == 0) return 0;
        --works[maxIndex];
    }

    return works.Select(s => (long)s * s).Sum();
}

짧은 문제지만 효율성 테스트가 존재하기 때문에 루프문 내에서 정렬하는 방식으로는 통과하지 못한다.

당연히 가장 효율적인 구조는 힙 트리를 구현하는 거겠지만 1씩 차감한다는 점에서 앞부터 탐색하는 방식으로도 충분히 통과한다.