99클럽 코테 스터디 5일차 TIL + 프로그래머스/2/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회입니다.

 

<코드>

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K: # 가장 적은 스코빌 지수가 K보다 작을 때 까지 반복
        
        if len(scoville) < 2 :
            return -1
        
        least_value = heapq.heappop(scoville)
        less_value = heapq.heappop(scoville)
        mixed = least_value + (less_value * 2)
        
        # 문제 잘못이해 "모든 음식이 K이상일 때 임"
        # if mixed >= K :
            # break;
        # else :
        heapq.heappush(scoville, mixed)
        answer += 1
            
    return answer

1. 아쉬운 것1

 

문제 이해를 잘못함.

scoville 리스트의 모든 값이 K보다 클것이 원래 내용인데, 잘못 이해함

 

최소 힙이므로 mixed가 K보다 크면 되는것으로 이해하였다

하지만 mixed가 k 보다 크다고 하더라도, heappush()를 하면 다시 힙정렬이 되어서 

리스트의 모든 값이 K보다 크다고 할수는 없다.

 

2. 아쉬운 것2

answer = +1 은 단순히 값 1을 넣는다는점임

 

3. 처음 생각

처음에는 우선순위큐에 대한 heapq를 몰라서 하마터면 큐로 모든것을 구현할 뻔 했다.

 

<모범사례>

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K: # while 대신에 이용
            break
        if len(scoville) == 0: # first 를 pop 했기 때문에 '== 0' 으로 가능
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2) # 식을 바로 합치는 방식
        answer += 1  

    return answer

- heappop()을 한번 한 후, 이것의 사후 효과로 두가지 조건문을 넣은방식도 좋은 고려방식이라고 봄

어차피 loop문을 돌려도 상관은 없을듯

 

<배운점>

1. 자료구조 최대힙, 최소힙 그리고 이것의 추상자료형이 우선순위 큐라는것을 더 체감하게 되었음

그리고 최소힙의 실질적 용도가 내가 당초에 생각한 스택이나 큐로 할수 없는것을 이용하게 됨으로서 알게 되었음

 

2. 우선순위 큐 이용에 관해서 배우게 됨

heapify, heappush, heappop 3가지 메소드가 익숙해짐

 

3. 우선순위 큐 구현은 3가지 방법임

그 중 힙은 데이터 삽입과 추출이 빈번할 때임

이번 문제도 최소 값 두가지를 추출하고, 한가지 값을 다시 삽입하는 방법임

이런점에서 힙으로 구현된 우선순위 큐가 좋음