[프로그래머스] 더 맵게 / python

1️⃣ 문제 설명

코딩테스트 연습 - 더 맵게

모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.

이를 위해, 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때,

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return

2️⃣ 풀이 전 계획과 생각

반복해서 최솟값과 두번째 최솟값을 찾아줘야 한다.

반복할 행위:

1. 배열을 sort 해준다.
2. first ← 제일 왼쪽 값을 뺀다.

second ← 그다음 왼쪽 값을 뺀다.

first + second * 2의 값을 다시 가장 왼쪽에 push 해준다.

1. 모든 음식의 스코빌 지수가 K 이상인지 체크해준다.

모두가 K이상이면 return count

아니라면, 다시 반복한다.

1. 길이가 1이고, 스코빌 지수가 K이상이 아니라면 -1을 return 해준다.

3️⃣ 풀이

def solution(scoville, K):
    answer = -1
    count = 0
    scoville.sort()
    while True:
        if len(scoville) == 1 :   break
        is_scoville = True
        count += 1
        first = scoville.pop(0)
        second = scoville.pop(0)
        scoville.insert(0, first + second * 2)
        scoville.sort()
        
        for one_scoville in scoville:
            if one_scoville < K :
                is_scoville = False
                break
        if is_scoville == True:
            return count
    return answer

4️⃣ 풀이하면서 막혔던 점과 고민

효율성 테스트에서 시간초과 나왔다. 어떻게하면, 간단하게 풀 수 있을지 고민해보자.

넣어주고 계속 sort해줘야 한다.

sort해 줄 필요없게 하기 위해, heapq 사용하자.

→ heap은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리다.

5️⃣ 풀이 후 알게된 개념과 소감

import heapq

def solution(scoville, K):
    answer = 0
    heqpq.heapify(scoville)
    
    while scoville[0] < K:
        mix = heapq.heappop(scoville) + heapq.heappop(scoville) * 2
        heapq.heappush(scoville, mix)
        answer += 1
        if len(scoville) == 1 and scoville[0] < K:
            return -1
    
    return answer

• scoville[0]은 항상 힙의 루트 노드로 최솟값이니 scoville[0]이 K보다 같아질때까지 반복문을 돌리자.
  → 반복문을 줄여줄 수 있었다.