문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
- 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
- Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
- Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- scoville의 길이는 2 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
풀이
문제 그대로 최소값이 주어진 K보다 작으면 혼합을 통해 scoville의 최소값이 K를 넘을때까지 반복하는 로직을 만들었고 예외상황에서는 -1을 출력하도록 하였다.
하지만 이렇게 문제를 풀었을때 정확도는 모두 맞았으나 다른 문제가 발생하였다.
효율성 테스트에서 시간초과를 해버린것.
그래서 이 문제가 힙(heap) 항목에 속한 문제라는것을 알게되어 힙을 찾게 되었다.
힙 - heapq
인터넷을 찾아보면 여러가지 어려운 말들이 많지만 결국 힙은 데이터를 항상 정렬된 형태로 저장하며 힙 리스트의 0번째 인덱스에는 항상 리스트의 최소값이 온다.
이러한 힙을 사용하기 위해서는 내장 모듈을 import해와야 한다.
import heapq
이제 heapq모듈의 함수를 사용할 수 있다.
heapq.heappush(heap, item)
힙 불변성을 유지하면서, item 값을 heap으로 푸시한다.
우선 heapq를 불러온뒤 리스트 a를 선언했다. 그 이후 heapq.heappush()를 통해 a에 9를 추가했더니 a의 가장 뒤에 추가된것을 볼 수있다. 여기서 a는 heapq이 아닌 단순한 리스트이기 때문에 추가적인 정렬은 없다.
이후 a에 리스트 내 가장 작은수보다 작은 수인 0을 추가하였고 리스트의 제일 앞에 추가된것을(heapq은 가장 작은 수가 인덱스 0에 해당된다.) 알 수 있다.
heapq.heapify(x)
리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.
리스트 a를 heapq로 전환하였다. 인덱스 0에 해당되는 값이 리스트 내 가장 작은 값인 0이 된것을 알 수 있다.
위의 heapq.heappush()를 사용해서 -99를 a에 추가하였더니 제일 앞에 추가된것을 알 수 있다. 하지만 a에 append()를 통해 -100을 추가하면 제일 뒤로 오는 모습을 볼 수 있다.
heapq.heappop(heap)
힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다.
heapq.heappop()를 통해 a를 넣었을때 -100이 아닌 인덱스 0번에 존재하던 -99가 출력되는것을 알 수 있다. 들어가있는 리스트가 heapq라는 가정 하에 인덱스 0에 존재하는 요소를 pop하는것으로 유추된다.
두번째 heapq.heappop()에서는 리스트가 앞선 heapq.heappop()를 통해 heapq로 정렬되어 가장 작은수인 -100이 인덱스 0으로 정렬되어 -100이 pop하는것을 알 수 있다.
heapq.heappushpop(heap, item)
힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환합니다. 결합한 액션은 heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적으로 실행합니다.
위의 heapq.heappush()이후 heapq.heappop()을 사용한것과 같다.
heapq.heapreplace(heap, item)
heap에서 가장 작은 항목을 팝하고 반환하며, 새로운 item도 푸시합니다. 힙 크기는 변경되지 않습니다. 힙이 비어 있으면, IndexError가 발생합니다.
위의 heapq.heappushpop()와 같은 값을 입력하였지만 다른값이 출력되었다. 연산 순서가 다른것을 알 수 있다.
문제 재풀이
위의 문제 풀이와 비슷하지만 heapq를 사용해서 문제를 풀었다.
효율성 테스트도 통과한 모습이다.
둘다 같은 while문을 사용해서 풀었으나 효율성의 차이가 왜 나타나는지에 대해서는 의문이 생긴다. 추측으로는 min으로 리스트 전체를 확인하는 과정이 생략되어 그럴것이라 조심스래 생각해본다.
