[프로그래머스] 야근 지수 by 파이썬 (Python)

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

프로그래머스

 

난이도 

LV 3

 

 

문제 설명

해야할 일이 works 배열에 각 일에 대한 필요 작업량이 저장되어 있다.

1시간에 작업량 1만큼을 할 수 있다.

퇴근 시간까지 남은시간 n 이 주어진다.

야근피로도는 퇴근 시간 이후 각 일의 남은 작업량의 제곱의 합이다.

가장 적은 야근 피로도를 계산해서 Return 해야한다.

 

 

접근 법

야근 피로도를 가장 낮추는 방법은 모든 일의 작업량을 균등하게 낮추는 것이다.

남은 퇴근시간 n 만큼 많은 작업량이 남은 작업부터 조금씩 줄여 나가야한다.

가장 많은 작업량이 남은 작업을 찾기 위해 heapq를 최대 heap으로 활용한다.

1. works를 heapq에 담는다.
2. heapq에 가장 앞의 작업이 가장 많은 작업량이 남아있는 작업이므로 퇴근시간 전에 한시간을 해결한다.
3. n -= 1을 해서 퇴근시간까지 남은시간을 줄인다.
4. 2,3번을 퇴근시간이 될때까지 계속 진행한다.
5. n = 0이되면 이제 야근 피로도를 계산해주면된다.
6. 만약 0 보다 작은 작업량이 있다면 야근이 없는 경우이다.
7. 야근 피로도를 return 해준다.

 

시간초과 해결

처음에는 heapq를 사용하지 않고 매번 정렬하여 가장 높은 작업량 -=1 을 해주었는데 효율성에서 시간초과가 발생했다.

따라서 어떤 방식으로 하면 시간초과를 해결할 수 있을지 고민하다 최소 힙인 heapq를 최대 힙으로 사용하여 매번 정렬하지 않아도 되도록 설계하면되지 않을까 하여 heapq를 이용해 해결하니 통과하였다.

 

 

 

코드

import heapq
def solution(n, works):
    heap = []
    for i in works:
        heapq.heappush(heap, (-i, i))
    answer = 0
    while n:
        x = heapq.heappop(heap)[1]
        x -= 1
        heapq.heappush(heap, (-x , x))
        n -= 1
    
    for w in heap:
        if w[1] < 0:
            return 0
        answer += w[1] ** 2
    return answer