[프로그래머스] 야근 지수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제를 풀면서 유효성 검사에서 자꾸 시간 초과가 발생하였다.

하여 최댓값을 더 빠르게 찾을 수 있는 최대 힙을 활용하여 문제를 해결하였다.

 

1. heap 자료구조를 사용하기 위해 heapq 모듈을 불러온다. import heapq
2. 만약 작업의 총량이 남은 시간 안에 다 할 수 있으면 if (sum(works) <= n)
3. 피로도는 없다. answer = 0
4. 반면에 작업을 남은 시간 안에 다 할 수 없다면 else
5. 최대 힙 정렬을 위해 작업 시간을 음수로 바꾸어 리스트를 새로 저장한다. works = [-i for i in works]
6. 새로 저장한 리스트를 heap 자료구조로 바꾼다. heapq.heapify(works)
7. 퇴근할 때까지 반복하며 while (n > 0)
8. 최대 힙에서 최댓값을 추출하고 그 값에 1을 더한 뒤(가장 많이 남은 작업을 1시간 수행), 해당 값을 최대 힙에 추가한다. heapq.heappush(works, heapq.heappop(works) + 1)
9. 1시간 동안 작업을 수행하였으므로 남은 퇴근 시간을 1시간 줄인다. n -= 1
10. 퇴근시간이 다 되었으면 남은 작업의 양을 하나씩 추출하여 야근 지수를 계산한다. for i in works: answer += i ** 2

반응형

3. 소스코드

import heapq

def solution(n, works):
    answer = 0

    if (sum(works) <= n):
        answer = 0
    else:
        works = [-i for i in works]
        heapq.heapify(works)
        
        while (n > 0):
            heapq.heappush(works, heapq.heappop(works) + 1)
            n -= 1
        
        for i in works:
            answer += i ** 2
        
    return answer