우선순위 큐 heapq

프로그래머스 연습문제 풀이 중 문제 해결

 

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

프로그래머스

 

 

어지간한 테스트케이스 다 제대로 나오는데 제출만 하면 틀리길레 오기로 찾아봄.

그 결과 왜인진 모르겠지만 heapq의 불안정성이 좀 있는듯?

heapq.heapify() 메소드 사용하면 heapq.sort()의 불변성이 생긴다고 함.

코드 참조

```python
import heapq

"""
heapq 이용
"""
def minimize(w,n):
    mw = [-i for i in w]
    """
    heapify 함수로 list -> heap 전환
    : heap.sort의 불변성 유지
    """
    heapq.heapify(mw)
    # print(type(mw))
    # print(mw)
    # wi = heapq.heappop(mw)
    # heapq.heappush(mw, wi)
    # print(mw)
    rn = n
    while rn>0:
        # print(mw)
        wi = heapq.heappop(mw)
        wi+=1; rn+=-1
        heapq.heappush(mw, wi)
        # if rn==0:
        #     break
    return mw

"""
무지성 sort 이용
"""
# def minimize(w,n):
#     w.sort(reverse=True)
#     # wi = heapq.heappop(mw)
#     # heapq.heappush(mw, wi)
#     # print(mw)
    
#     rn = n
#     while rn>0:
#         # print(mw)
#         w.sort(reverse=True)
#         w[0]-=1
#         rn+=-1
        
#         # if rn==0:
#         #     break
#     return w
        

def solution(n, works):
    if sum(works)<=n:
        answer = 0
    else:
        mw = minimize(works, n)
        sum_s = 0
        for mwi in mw:
            sum_s += mwi*mwi
        answer = sum_s
        print(mw)
    # print(answer)
    return answer