99클럽 코테 스터디 2일차 TIL + 힙 - 더 맵게

🔗 프로그래머스 - 더 맵게

 

 

힙을 사용해야 시간 초과가 일어나지 않는 문제였다.

 

<힙 복습  - 출처 : 파이썬 공식 문서>

heapq.heappush(heap, item)

힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.

heapq.heappop(heap)

힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하십시오.

heapq.heappushpop(heap, item)

힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환합니다. 결합한 액션은 heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적으로 실행합니다.

heapq.heapify(x)

리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

heapq.heapreplace(heap, item)

heap에서 가장 작은 항목을 팝하고 반환하며, 새로운 item도 푸시합니다. 힙 크기는 변경되지 않습니다. 힙이 비어 있으면, IndexError가 발생합니다. 이 한 단계 연산은 heappop()한 다음 heappush()하는 것보다 더 효율적이며 고정 크기 힙을 사용할 때 더 적합 할 수 있습니다. 팝/푸시 조합은 항상 힙에서 요소를 반환하고 그것을 item으로 대체합니다. 반환된 값은 추가된 item보다 클 수 있습니다. 그것이 바람직하지 않다면, 대신 heappushpop() 사용을 고려하십시오. 푸시/팝 조합은 두 값 중 작은 값을 반환하여, 힙에 큰 값을 남겨 둡니다.

 

1. 처음에 무시하고 min()을 이용했는데 아니나 다를까 시간 초과가 떴다.

2. 예외 처리를 제대로 해주지 않아 테스트 케이스 하나를 통과하지 못했다. - 목표한 바를 이루지 못했을 때 반복문 탈출

        if len(scoville) == 0:
            if min >= K:
                return count
            return -1