[python/힙] 35. 더 맵게(feat. heapq 모듈)

문제 출처

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

문제 설명

매운 것을 좋아하는 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 합니다.

 

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

 

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

---

나의 코드(실패, 효율성 0으로 정확성 76.2)

def solution(scoville, K):
    answer = 0
    while True:
        if all(x>=K for x in scoville):  #scoville의 원소가 모두 K볻 크다면 answer을 반환하고 코드를 종료한다.
            return answer
        if len(scoville) == 1 and scoville[0] < K:  #coville의 원소가 하나 남았고, 그것이 K보다 작다면 -1를 반환한다.
            return -1
        scoville = sorted(scoville)  #scoville을 오름차순으로 정렬한다.
        m = scoville.pop(0)  #가장 작은 원소를 m으로, 그 다음으로 작은 원소를 n으로 설정한다.
        n = scoville.pop(0)
        scoville.append(m + 2*n)  #m+2*n을 계산하여 scoville라는 리스트에 붙여준다.
        answer += 1  #count

효율성을 높일 수 있는 방법을 생각하지 못해서 결국 다른 사람들의 풀이를 보기로 했다 ㅠㅠ

heapq를 사용하지 않으면 효율성을 통과하지 못하는 것 같다.

 

다른 풀이

import heapq as hq

def solution(scoville, K):
    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K:
            break
        if len(scoville) == 0:
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1
    return answer

기본적인 아이디어에는 차이가 없으나 나는 매 loop마다 정렬을 수행했기 때문에 효율성에서 문제가 생겼던 것 같다.

heap은 알아서 리스트를 정렬해주기 때문에 이 부분에서 효율성을 크게 높일 수 있었던 것이 아닌가 싶다.

즉, 앞으로 매번 정렬이 필요하고 이를 통해 최소값, 최댓값을 반환해야하는 문제라면 힙 정렬을 사용해보자!

 

 

* 힙 정렬

: 힙 정렬은 시간 복잡도가 좋은 편이다.(시간복잡도: O(nlog2n)) 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 힙 정렬을 사용하면 좋다. 아래의 그림은 '최대 힙의 삽입'의 경우로, 다음과 같이 전 이진 트리를 이용한 정렬 방식을 사용한다.

 

출처: https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

 

* heapq 모듈 사용법(출처: www.daleseo.com/python-heapq/)

- heapq 모듈은 이진 트리 기반의 최소 힙(min heap) 자료구조를 제공한다.

 

1) 힙에 원소 추가

이와 같이 heappush함수 첫번째 인자에 추가하고 싶은 리스트를 입력하고 두번째 인자에 추가할 원소를 입력한다.

 

2) 힙에서 원소 삭제

원소를 삭제하고 싶다면 heappop함수를 이용해서 삭제할 수 있다. 위 코드와 같이 가장 작았던 1이 삭제되어 리턴된 것을 확인할 수 있다.

 

3) 기존 리스트를 힙으로 변환

이미 원소가 들어있는 리스트를 힙으로 만들려면 heapify라는 함수를 이용하면 된다.