[프로그래머스 - 힙(Heap)] 더 맵게 (Python3)

https://school.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회입니다.

풀이

먼저 문제의 요구사항대로만 코드를 구현했다.
scoville을 정렬하고, 스코빌 지수가 가장 낮은 두 값이 K보다 작으면 섞어줬다.
뽑은 두 값을 없애고 새로 조합한 값을 넣어주며 scoville의 최소값이 K이상이 될 때까지 반복해준다.

def solution(scoville, K):
    answer = 0
    scoville.sort()
    
    while scoville[0] < K:
        scoville.sort()
        if scoville[0] < K and scoville[1] < K:
            a,b = scoville[0], scoville[1]
        else:
            answer = -1
            break
        new = a + (b*2)
        scoville = scoville[2:]
        scoville.append(new)
        answer += 1
    return answer

예시 몇개는 맞는데 역시 시간초과가 났다.

힙(Heap)

힙은 최소 힙과 최대 힙으로 나뉜다.

• 최소 힙 : 부모가 자식 노드보다 작음, 가장 작은 값부터 추출
• 최대 힙 : 부모가 자식 노드보다 큼, 가장 큰 값부터 추출

출처 : https://passwd.tistory.com/322

풀이를 찾아보니 파이썬에서는 heapq 라이브러리로 힙 사용이 가능했다.

• heapify() : 리스트를 힙으로 바꿔줄 수 있고,
• heappush(heap, item) : 힙에 값 추가
• heappop(heap) : 힙에서 값 추출

heapq에서는 최소 힙만 지원된다고 한다. (부호를 바꿔주는 등의 방법으로 최대 힙 구현 가능)

heapq 사용 풀이

from heapq import *
def solution(scoville, K):
    answer = 0
    heapify(scoville)
    while scoville[0] < K and len(scoville) > 1:
        a = heappop(scoville)
        b = heappop(scoville)
        new = a + (b*2)
        heappush(scoville, new)
        answer += 1
    if scoville[0] < K:
        answer = -1
    return answer

scoville을 heap으로 만들어주고 최소값이 K보다 작다면 계속 반복해준다. 하지만 두개를 뽑기 때문에 scoville의 길이가 1보다는 커야 한다.
heappop()으로 가장 작은 스코빌 지수 값 2개를 뽑고 새로 조합해서 heappush로 힙에 추가해준다. 그때마다 횟수를 카운트해준다.
while문이 다 끝났을 때 scoville의 최소값이 K보다 작다면 음식이 한개만 남을때까지 섞어도 K보다 작은 경우이므로 -1을 리턴해준다.

좋은 점수는 아닌것 같은데 암튼 풀었다.

처음에는 스코빌 지수가 K보다 작은 음식만 섞어야 하는줄 알고 이에 맞는 조건을 주고 풀었다.
하지만 풀이는 맞는 것 같은데 틀리는 테케가 많이 나와서 가장 작은 스코빌 지수가 K보다 작다면 무조건 두개를 뽑아서 계산하도록 하니까 풀렸다.
섞을 음식의 스코빌 지수는 K보다 작은게 하나라도 있기만 하면 됐던 것 같다.