[C#] 야근 지수

야근 지수

문제 설명

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

풀이

public class OvertimeScoreCalculator
{
    public long Solution(int n, int[] works) {
        long answer = 0;
        
        List<int> worksList = works.ToList();
        worksList.Sort();
        worksList.Reverse();
        
        int currentIndex = 0;
        int maxIndex = 0;
        
        int time = n;
        
        while (time > 0)
        {
            //현재 확인한 값이 최대값과 같을 경우 현재 확인한 값이 최대 값이므로 해당 값을 1 감소
            if (worksList[currentIndex] >= worksList[maxIndex])
            {
                worksList[currentIndex] = worksList[currentIndex] > 0 ? worksList[currentIndex]-1 : 0;
                time--;
            }
        
            if (worksList[currentIndex] > worksList[maxIndex])
            {
                maxIndex = currentIndex;
            }
        
            if (worksList[currentIndex] <= worksList[maxIndex])
            {
                currentIndex = currentIndex + 1 < worksList.Count ? currentIndex + 1 : 0;
            }
        }
        
        
        foreach (int i in worksList)
        {
            answer += (long)Math.Pow(i, 2);
        }
        
        return answer;
    }
    
}

접근 방법

works의 값을 각각 제곱해서 더한 것이 최소가 되게 해야하므로 works 배열 내에 값들의 편차를 줄이는 것이 중요하다고 판단
1. 배열을 리스트로 변환 (Sort() 기능을 사용하기 위해)
2. 해당 리스트를 반전 (가장 큰 값이 제일 앞에 오도록 하기 위해)
3. n만큼 반복하며 리스트의 가장 앞에 있는 값을 1 감소
4. 감소 후 다시 리스트 정렬 + 반전

이러한 방식을 사용해 답은 찾을 수 있었으나 효율성 문제를 맞닥뜨림

• 반복문 내에서 정렬 및 반전을 실시하므로 시간복잡도가 높아짐

문제 해결

		while (time > 0)
        {
            //현재 확인한 값이 최대값과 같을 경우 현재 확인한 값이 최대 값이므로 해당 값을 1 감소
            if (worksList[currentIndex] >= worksList[maxIndex])
            {
                worksList[currentIndex] = worksList[currentIndex] > 0 ? worksList[currentIndex]-1 : 0;
                time--;
            }
        
            if (worksList[currentIndex] > worksList[maxIndex])
            {
                maxIndex = currentIndex;
            }
        
            if (worksList[currentIndex] <= worksList[maxIndex])
            {
                currentIndex = currentIndex + 1 < worksList.Count ? currentIndex + 1 : 0;
            }
        }

• 결국 n회 동안 최댓값을 찾아 1씩 줄이는 동작을 실시하는 것이 중요
  어떻게 최댓값을 찾는 로직을 단순화할지 고민
• 먼저 시작시 정렬 및 반전을 1회 실시
  시작시 0번 자리에 최댓값이 위치
• 이후 확인하고 있는 인덱스 currentIndex의 값이 최댓값의 인덱스maxIndex의 값보다 크거나 같다면 해당 위치가 최댓값이므로 1 감소하고 time을 1 감소
• 해당 조치로 인해 현재 검사 중인 값과 최댓값이 같거나 작다면 다른 값을 확인하기 위해 다음 인덱스 번호를 확인하도록 함
• 다른 인덱스 번호를 확인하다가 해당 위치에 있는 값이 기존 최댓값 보다 크다면 maxIndex를 갱신
• 해당 과정을 반복하게 함으로써 시간 복잡도를 줄여 기준을 통과할 수 있었으나 더 나은 개선 방향이 없을지는 추가 학습 필요