Programmers / 야근 지수 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 야근지수 (3단계), 힙 heap

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

문제 설명

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

제한 사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

입출력 예worksnresult

[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1,1]	3	0

입출력 예 설명

입출력 예 #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입니다.

입출력 예 #3

남은 작업량이 없으므로 피로도는 0입니다.

---

나의 풀이

 

우선 야근 지수를 구할 때 작업 시간이 많이 걸리는 작업(최대값)을 1씩 빼주면 되는데, 해당 값을 찾는 과정에서 효율성이 떨어지는 것 같다.

효율성을 개선하려면 힙 자료구조를 사용해야한다.

 

def solution(n, works):
    if sum(works) <= n:
        return 0
    while n > 0:
        num = works.index(max(works))
        works[num] = works[num] - 1
        n -= 1
    return sum([i*i for i in works])

 

 

나의 풀이 (2번째 풀이 - heapq 이용)

import heapq as hq
def solution(n, works):
    if sum(works) <= n:
        return 0
    works = [(-1) * i for i in works]
    hq.heapify(works)
    while n > 0:
        tmp = hq.heappop(works) + 1
        hq.heappush(works,tmp)
        n -= 1
    print(works)
    return sum([i*i for i in works])

파이썬 모듈에서 구현된 힙은 최소힙 기반으로 구현되어있어서 리스트에 음수를 취해서 힙 구조를 만들어야한다

hq.heapify(list) : 이미 생성된 리스트를 힙 자료구조로 변환해줌

hq.heappush(list,value): 힙이 된 list에 새로운 값 value를 추가해서 새로 힙 정렬한다

 

힙 자료구조에 대한 자세한 설명 글 참고

https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

 

내 블로그에서 힙에 대한 글 참고

https://sillon-coding.tistory.com/197

문제 / 최대힙 / Python 파이썬

https://sillon-coding.tistory.com/149

[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap) / Python 파이썬

---

※ 알아야 할 것

힙 함수 활용하기

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )