LV3. [연습문제] 야근 지수

https://school.programmers.co.kr/learn/courses/30/lessons/12927

접근

• works리스트의 원소를 제곱하여 더한값이 야근 피로도가 된다.
• 숫자가 클수록 제곱의 값이 커지기 때문에, 가장 큰 숫자를 줄이는것이 중요하다.
• n만큼 작업할 수 있고, 이를 반복문으로 사용할 수 있을 것이다.
• 다만, n번마다 최대값을 확인하면 len(works)==m, O(m*n)의 시간이 걸릴 것이다. 이를 줄이는 방법으로 생각해보자.

코드

def solution(n, works):
    answer = 0

	# 만약 잔업이 야근 할 시간보다 작다면, 남은 야근지수가 0일 것이다.
    if n < sum(works):
    	# works 리스트를 정렬한다. O(nlog(n))
        works.sort()
		
		# 리스트를 정렬했으니, 가장 큰수는 제일 뒤에 있을 것이다.
        idx = len(works)-1

        while n > 0:
        	# idx가 가리키는 곳을 1 줄인다.
            works[idx] -= 1
            n -= 1

			# 다음 idx 를 미리 설정해준다.
            next_idx = idx-1 if idx>0 else len(works)-1

            # 다음 idx의 값보다 현재 idx값이 더 작으면 idx를 다음 idx로 옮겨준다.
            # 맨 뒤에서 한칸씩 앞으로 가며 줄이는 것이다.
            if works[idx] < works[next_idx]:
                idx = next_idx

            # 만약 다음 idx가 같거나 현재보다 작으면 다시 뒤로가서 줄이기 시작한다.
            else:
                idx = len(works)-1 

		# 마지막으로 works리스트의 원소를 제곱해서 더한다.
        while works:
            answer += works.pop()**2

    return answer