[프로그래머스💯] 코딩테스트 연습 > 연습문제 > 야근 지수 / Python 문제풀이

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

import heapq


def solution(n, works):
    maxHeap = []
    for w in works:
        heapq.heappush(maxHeap, -w)
    while n > 0:
        DoWork = -heapq.heappop(maxHeap) - 1
        if DoWork == -1:  # 할일을 다함
            return 0
        heapq.heappush(maxHeap, -DoWork)
        n -= 1
    res = 0
    for fatigue in maxHeap: # 남은 일 피로도 계산
        res += fatigue ** 2 
    return res

 

풀이)

 

3단계 문제치고 난이도가 쉽다.

 

1. 가장 많이 남은일을 먼저하는게 항상 최종 피로도를 줄여준다.

(그리디하게 구현 가능)

 

2. 그러므로 현재 가장 많이 남은일을 계속 반복하면 된다.

 

종료조건 :

- 남은일이 없다.

- n 시간을 다 썼다.

 

제일 많은 일을 효율적으로 골라내기 위해 MaxHeap 구조를 이용한다.

 

---

파이썬 heapq 모듈을 minHeap 이 아닌 MaxHeap 으로 이용하는 방법:

 

파이썬 heapq 모듈은 기본적으로 minHeap 을 지원한다.

heappop() 으로 꺼낼 때 항상 최소가 꺼내진다는 뜻이다.

따라서, MaxHeap 으로 쓸 때는 집어넣을때 우리가 원하는 값에 - 를 붙여서 집어넣는다.

그러면 꺼낼 때 원래 우리가 원하는 값은 원래 가장 크던 값이 나온다. (-를 붙였으므로 가장 큰값이 가장 작은 값이 된다.)

그럼 꺼낸 후에 다시 - 를 붙여주면 원래 우리가 원하던 값이 된다.

 

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.