[프로그래머스] 더 맵게

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42626

📰 문제 요약

문제 설명, 입력, 출력, 조건 등 간략하게 정리

• 모든 음식의 스코빌 지수 K 이상으로 만들기 위해, 스코빌 지수가 가장 낮은 두 개의 음식을 아래 방버으로 섞어 새로운 음식을 만든다.

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

• 모든 음식이 K 이상이 될 때까지 반복하여 섞는다

입력

• scoville : 모든 음식의 스코빌 지수를 담은 배열 (2 ≤ scoville의 길이 ≤ 1000000)
• K : 원하는 스코빌 지수 (0 ≤ K ≤ 1000000000)

출력

• 원하는 스코빌 지수를 위해 섞어야 하는 최소 횟수
• 모든 음식을 만들 수 없는 경우에는 -1을 반환

🔓 문제 접근 방식

기본 아이디어

• 코드 구성 자체는 간단하지만, 시간복잡도를 최소화하는 게 제일 중요하다고 생각했다.
• 가장 작은 값 2개를 사용해야 하기 때문에 최소 힙을 사용
• 또한 K를 달성했을 경우, pop을 통해 원소 삭제 해주는 과정 추가

사용 알고리즘

• 힙 (heap)

💻 구현 방법

1. scoville리스트를 haep으로 변환
2. while문으로 새로운 음식 만들기 (모든 음식의 스코빌 지수가 K 이상이 되거나 더이상 섞을 음식이 없을 때까지)
3. 새로운 방법으로 음식 만들기
4. 새롭게 만든 음식의 스코빌 지수 추가
5. 횟수 계산

👍🏻 최종 제출 코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) # scoville을 heap 형태로 변환
    while len(scoville) > 1 and scoville[0] < K:
        # 새로운 음식 만들기
        mix = heapq.heappop(scoville) + heapq.heappop(scoville) * 2
        # 새롭게 만든 음식의 스코빌 지수 추가
        heapq.heappush(scoville, mix)
        answer += 1 # 횟수 추가
    
    # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1 반환
    if scoville[0] < K: 
        return -1
    return answer

📝 새로 학습한 내용

파이썬에서 힙 구현

heapq 모듈을 통해 최소 힙을 쉽게 구현할 수 있음

• heapq.heappush(heap, item) : 힙에 새 값을 삽입
• heapq.heappop(heap) : 힙에서 가장 작은 값을 제거하고 반환
• heapq.heapify(list) : 리스트를 힙 구조로 변환

→ 또한 정직하게 heapq를 계속 쓸 필요 없이, import heapq as hq 를 활용하면 보다 간결하게 사용할 수 있다