힙 (Heap)
최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.
파이썬은 heapq 모듈을 사용해서 힙을 사용할 수 있다.
import heapq # 기본적으로 min heap heapq.heapify(heap정렬할 대상) # 리스트를 heap으로 변환 heapq.heappush(heap 대상, 추가할 값) heapq.heappop(heap 대상) # 가장 작은 원소를 없앤 후 그 값을 반환
만약 최대 힙을 만들려고 한다면
heapq.heapify를 할 때 리스트를 -1를 곱해서 하면 된다. (부호 바꾸기)
그리고 heapq.heappop을 할 때 다시 -1을 곱하면 된다. 그 값들을 차례대로 append하면 내림차순으로 정렬된 리스트가 나오게 된다.
문제
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
어떻게 해야할까
스코빌 지수 K 이상 만들기 (꽤나 맵당당인 것같다 부럽)
K 이상이 될때까지 계속해서 섞는 최소 횟수 구하기 문제.
일단 입력의 리스트를 sort해야겠다. 바로 전에 포스팅한 문제와 비슷한 것같기도..? 근데 애초에 힙으로 풀라고 틀을 주긴했다. Heap 다 까먹었는데 ㅠ 우선 처음에 준 코드를 찬찬히 이해해보도록 하자.
리스트를 sort하는게 아니라 힙을 통해서 가장 작은 스코빌 지수를 뽑는 것이었다. 여기서 뭘 더 건드려야하는 거지?
코드
(다시 보니 전에 내가 풀었던건가? 초기화하니까 틀이 날라가는거보면 과거의 내가 했던건가..?? 생각해보니 그랬던 듯하다.. 그래서 다시 한번 코드를 다 지워보고 해보도록 한다.)
흠.. 근데 아무래도 힙으로 푸는게 더 와닿는 듯하다. 힙 모듈을 사용해서 다시 차근차근 코드를 짜보자. 아마 O(nlogn)은 안되는 듯 하다. O(n)을 목표로 다시 짜보자..라고 생각하고 해보는데 잘 되질 않는다.
아까보단 테케를 통과하긴했는데 아직 멀었다 :(
효율성 테스트는 모두 통과한 것을 보면 내가 고려하지않은 예외케이스만 찾으면 될 듯하다. 아 생각해보니 -1일 경우를 내가 고려안했다.
딱 하나만 통과하면 된다. 아마 -1 리턴하는 부분을 내가 어디 놓친 듯 하다.
최종코드
예외케이스를 다 잡았다.
.gif)