이진트리 기반의 최소합 자료구조를 제공하는 heapq 모듈을 사용할 수 있는지 보는 문제이다.
heapq는 Java의 PriorityQueue 클래스와 유사하다.
heapq를 사용하는 방법은 우선 빈 리스트를 만들고,
heapq 모듈을 이용해 원소를 추가하거나 삭제한 리스트가 최소 힙이 된다.
추가 시에는 heappush, 삭제 시에는 heappop을 사용한다.
heappop 사용 시에는 가장 작은 원소가 삭제된다.
기존 리스트를 힙으로 만들고 싶은 경우에는 heapify를 사용해도 좋다.
시간 복잡도가 원소 수에 비례하기 때문에 for문 안에서 heappush 이용하는 것과 시간은 비슷할 듯하다.
문제의 내용은 가장 낮은 스코빌 지수 + 두번째로 낮은 스코빌 지수x2 의 값을 갱신함으로써
모든 스코빌 지수를 K 이상으로 만드는 것이다.
heap에서는 오름차순으로 정렬이 되기 때문에 리스트 0번째가 K 이상이면 된다.
따라서 0번째 값이 K보다 크면 종료하는 while문을 넣어주고, except면 -1을 리턴해서 런타임 에러를 방지한다.
'공부 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 42577번 (0) | 2022.06.15 |
|---|---|
| [프로그래머스] 42840번 (0) | 2022.06.15 |
| [프로그래머스] 42746번 (0) | 2022.06.15 |
| [프로그래머스] 42748번 (0) | 2022.06.15 |
| [프로그래머스] 43165번 (0) | 2022.06.15 |
