프로그래머스 - 더 맵게(힙(heap))

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

 

# 풀이

- 힙(heap) 구조를 이용하여 스코빌 지수가 K보다 미만인 값들을 담았다.

- 생성한 힙 구조는 자동으로 오름차순 정렬을 해줌으로 heappop으로 가장 작은 값을 꺼내 K보다 작으면 연산을 수행하고 다시 힙 구조에 넣는다.

- 만약 가장 작은 값이 K보다 커지면 반복문을 나오고 연산 횟수(cnt)를 return 한다.

import heapq

def solution(scoville, K):
    h = []
    for s in scoville:
        if s <= K:
            heapq.heappush(h, s)
    
    cnt = 0
    while h:
        tmp = heapq.heappop(h)
        if tmp > K:
            break
        if tmp <= K:
            tmp += (heapq.heappop(h)*2)
            heapq.heappush(h, tmp)
            cnt += 1
    return cnt

- 런타임 에러가 발생했다.

 

# 고찰

- 만들 수 없는 경우 -1을 return 해야하는 것을 고려하지 않았다.

- tmp라는 변수를 따로 사용하면 메모리를 사용하고 연산을 한 번 더 하는 것이므로 사용하지 않는 방법으로 풀어야 한다.

 

# 수정한 풀이

- 연산을 수행하기 전에 수행되지 않는 조건들을 미리 처리하고, 수행해야 할 조건이 되면 연산을 수행하고 횟수를 카운트해준다.

- tmp 변수를 사용하는 대신 heappop을 연속으로 수행하였다.

  -> 런타임 에러 해결

import heapq

def solution(scoville, K):
    h = []
    for s in scoville:
        if s <= K:
            heapq.heappush(h, s)
    
    cnt = 0
    while True:
        if len(h)<=1 and h[0]<K:
            return -1
        if h[0] > K:
            break
        if h[0] <= K:
            heapq.heappush(h, heapq.heappop(h) + (heapq.heappop(h)*2))
            cnt += 1
    return cnt