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

프로그래머스 '더 맵게' 문제 풀이입니다.

 

문제 링크

코딩테스트 연습 - 더 맵게

● 문제 간단 설명

배열 내 요소 모두 특정 스코빌을 넘을 때까지 가장 작은 값과, 두 번째로 작은 값을 조합하고, 모든 요소가 특정 값(K)을 넘었을 때, 조합한 횟수를 return 하는 문제

 

● 문제 해결 방향

처음에는 문제 설명에서 주어진 대로 값을 정렬하고, k값과 비교하고, 작은 수 2개를 조합하는 과정을 반복하는 코드를 작성했다.

정확성 부분에서는 쉽게 통과할 수 있었지만, 효율성 부분에서는 당연히 시간 초과가 발생했다.

 

파이썬에서 제공하는 heapq라는 내장 라이브러리를 사용하여 문제를 해결하였고, heap 알고리즘에 따라 값을 정렬하고, 제거하고, 삽입할 수 있어서 효율성 문제도 통과할 수 있었다.

 

● 문제 해결 코드

import heapq

def solution(scoville, k):
    answer = 0
    heapq.heapify(scoville)

    while scoville[0] < k:
        if len(scoville) == 1: return -1

        heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville) * 2)
        answer += 1


    return answer

heapq.heapify()를 통해 먼저 scoville 배열을 힙 정렬을 실시한다.

힙 정렬된 배열의 0번째 인덱스 값이 최소값이기 때문에 0 번째 값이 k를 넘지 못하면 계속 반복하도록 while 반복문을 사용하였다.

 

반복문 내부에서는

길이가 1일 경우 더 이상 값을 조합할 수 없기 때문에 문제의 설명에 따라 -1을 return 해주었다.

그 외의 경우에는 heapq.heappop()을 2번 사용하여 가장 작은 수, 두 번째 작은 수를 뽑아내어 조합해주었다.

조합한 값을 heapq.heappush()를 통해 쉽게 배열에 넣을 수 있었다.

 

heap을 직접 구현해보려고 했지만 이번 문제에서는 실패했다.

heap 알고리즘에 대한 내용을 정리하면서 한번 더 시도해 보려고 한다.

 

● 참고

[파이썬] heapq 모듈 사용법