[문제 풀이] 더 맵게

코딩테스트 연습 - 더 맵게

해결 과정

 모든 원소가 K 이상이 되도록 처리하는데, 처리하는 최소 횟수를 구하는 문제

 일단, scoville가 정렬되어 있다는 조건이 없다는 것을 확인했다.  처음에는 정렬한 뒤에 최솟값, 최댓값을 해야 하나 생각해서 그렇게 구현했는데 최소 횟수가 안나왔다. 예시 조건 설명을 다시 살펴보니, 최솟값, 그다음 최솟값을 대상으로 계산하면 가장 최소 횟수를 구할 수 있다는 것을 알고는 이렇게 구현해서 풀었다. 

 추가로, 처음부터 heap을 생각한 것은 아니고, for 문이나 while문을 돌 때마다 정렬을 해야 했는데 무작정 사용하면 효율성 테스트에서 실패하겠다 싶었다. 마침 heap 주차이기도 하고 heap이 데이터를 정렬된 상태로 사용하는 자료구조 라는 것을 알고 있어서 python의 heapq 모듈을 찾아서 사용했다.

나의 풀이

import heapq

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

    while len(scoville) != 1:
        newScoville = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
        heapq.heappush(scoville, newScoville)
        answer += 1

        if scoville[0] >= K:
            return answer
    
    answer = -1
    return answer

 

다른 풀이

다른 풀이도 비슷하게 풀었다.

 

IDEA

python의 heapq 모듈