1. 문제

Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution 완성하기

2. 조건

• 야근 피로도 = 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값
• works는 길이 1 이상, 20,000 이하인 배열⭐
• works의 원소는 50000 이하인 자연수⭐
• n은 1,000,000 이하인 자연수

3. 출력 예시

예시1)
n=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 4시간동안 일을 한 결과: [2, 2, 2]
야근 지수 = 22 + 22 + 22 = 12

예시2)
n=1일 때, 남은 일의 작업량이 [2,1,2]라면 야근 지수를 최소화하기 위해 1시간동안 일을 한 결과: [1,1,2]
야근지수 : 12 + 12 + 22 = 6

4. 코드 구현

4-1. 비효율적인 코드 구현 예시

초반에 접근했던 방식으로도 케이스 통과는 가능했으나, 효율성 측면에서 시간 초과 에러가 발생했다.

위의 주석처리 부분이 처음에 리스트를 내림차순 정렬한 후 최대값을 꺼내고, 1씩 줄여나가는 방법으로 작성한 방식이다.
works는 길이 1 이상, 20,000 이하인 배열이고, 원소는 50000 이하인 자연수라는 조건을 고려한다면, 해당 코드로 인해 다음과 같은 문제가 발생할 수 있다.

• while n > 0: 루프마다 works.sort(reverse=True)를 실행함
• sort()는 O(k log k) 시간복잡도(여기서 k는 works의 길이)로, n이 매우 크면 전체 시간복잡도가 O(nk log k)가 되어 시간초과가 발생함

4-2. 개선된 코드 (heapq 활용해 시간 초과 개선)

이후, 서치를 통해 파이썬 heapq로 최대 힙 구현 방법에 대해 알게 되었다.

💡 파이썬의 heapq 모듈은 기본적으로 최소 힙(min heap)만 지원하고,
최소 힙은 항상 가장 작은 값이 루트(인덱스 0)에 위치한다.

주요 함수
heapq.heappush(heap, item): 힙에 원소 추가
heapq.heappop(heap): 힙에서 가장 작은 원소 제거 및 반환
heapq.heapify(list): 리스트를 힙 구조로 변환

코드 구현 프로세스

1. 전체 작업량 합계 계산
   works 리스트에 있는 모든 작업량을 더해 total 변수에 저장한다.

2. 최대 힙(max heap) 생성
   최대 힙 구현을 위해 각 작업량을 음수로 변환하여 max_heap에 저장한다.

3. n번 동안 작업량 줄이기
   매 반복마다 최대 힙에서 가장 큰 작업량을 꺼내 1만큼 줄이며, n이 0이 될 때까지 반복한다.

4. 야근 피로도 계산
   모든 작업량의 제곱을 더해 최종 피로도를 계산한다.
   (음수로 저장된 값이므로, 꺼낼 때는 제곱하면 양수가 됨)

5. 결과 반환
   계산된 야근 피로도를 반환한다.

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