프로그래머스 (Level 2) : 더맵게 / Python, heapq, try-except

문제

코딩테스트 연습 - 더 맵게

 

프로그래머스 heap 카테고리에 있는 문제이다. 두번이나 힙이 아닌 다른 자료구조로 푸는 뻘짓을 했다가 .. 

파이썬 힙 자료구조 (heapq)를 공부하며 반성했다 ㅠㅠ 

 

 

풀이1 (실패 : deque - 정확도 100, 효율성 0)

from collections import deque
def solution(scoville, K):
    cnt = tmp = 0

    scoville.sort()
    dq = deque(scoville)
    while 1:
        if dq[0]>=K: return cnt
        if cnt==len(scoville)-1: return -1
        
        if dq[0]<K:
            tmp = dq[0]+(dq[1]*2)
            dq.popleft()
            dq.popleft()
            dq.appendleft(tmp)
            cnt+=1
        
        dq = deque(sorted(dq))

 

자주 쓰는 자료구조인 deque로 풀곤 효율성 시간초과가 나서

혹시 pop을 계속해주는게 문제일까 싶어 리스트로 풀어봤다.

 

 

풀이2 (실패 : list - 정확도 100, 효율성 0)

def solution(scoville, K): 
    cnt = tmp = 0
    scoville.sort()
    sc=scoville
    while sc[0]<K:
        if cnt==len(scoville)-1: return -1

        tmp = sc[0]+(sc[1]*2)
        if len(sc)>2:
            sc=sc[2:]
            sc.insert(0,tmp)
        else:
            sc.insert(0,tmp)
            sc=sc[0:1]
        cnt+=1      
        sc.sort()
    return cnt

 

고작 그런 문제가 아니었고,.. 매번 sort하는 부분이 문제였다.

심지어 슬라이싱 하는게 pop보다 더 느리다고 한다...TT

(웬만해선 리스트보다 데큐가 빠름,, > https://brownbears.tistory.com/452, https://wellsw.tistory.com/122 )

 

 

파이썬의 heap 자료구조인 heapq는 이진트리 구조인데 항상 최소힙의 상태를 유지한다!

(최소힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙)

=> 항상 정렬상태 => 이 문제에서 효율성을 위해 heap을 사용해야 하는 이유..

 

 

풀이3 (성공 : heap - 정확도 100, 효율성 100)

import heapq as h
def solution(scoville, K): 
    cnt = tmp = 0
    hq=scoville #s리스트 복사 
    h.heapify(hq) #heapq 리스트로 생성 
    
    while hq[0]<K:
        try: h.heappush(hq, h.heappop(hq)+(h.heappop(hq)*2))
        except IndexError: return -1
        cnt+=1
    return cnt

 

heapq 라는 내장 라이브러리를 사용했다. 

 

heapq.heappush(리스트, 값)
heapq.heappop(리스트, 값)
heapq.heapify(리스트)

 

이런 식으로 사용해야 하기 때문에 import 할때 heapq자료구를 h로 별칭을 지었고

초기에 heapify() 메소드로 바로 리스트로 heapq를 초기화 했다.

파이썬 알고리즘에서 try-except 문도 처음 사용해봤는데 앞으로 유용하게 사용할 것 같다.

 

 

무지성으로 코딩하는걸 반성하자...

 

---

Reference

[Python] 리스트 slice, pop, del 성능 비교 및 사용방법

 

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

 

[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)

05-4 예외 처리