[프로그래머스_힙_Lv2] 더 맵게

더 맵게

문제 링크

나의 풀이

🙅‍♂️ 첫 번째 풀이(완전 오답)

def solution(scoville, K):
    count  = 0
    low = []
    while min(scoville) <= K:
        low.append(scoville.pop(scoville.index(min(scoville))))
        low.append(scoville.pop(scoville.index(min(scoville)))*2)
        scoville.append(sum(low))
        count += 1
    return count

• 채점 결과 몇 개의 테스트 케이스는 통과하였으나 완전히 틀린 답안이었다. 좀 더 효율적인 코드 작성을 위해 아직은 익숙하지 않은 heapq 모듈을 사용하여 전면 수정하기로 하였다.

🙅‍♂️ 두 번째 풀이(정확도 100%, but 효율성 테스트 실패)

import heapq


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

• 파이썬이 제공하는 heapq 모듈을 사용하여 코드를 작성하였다.
• scoville 배열을 heapify한 후 while 반복문을 통해 scoville
  배열의 최솟값이 K 이상일 경우 count를 리턴하고, 아닐 경우 heapq.heappop() 메서드를 통해 가장 작은 두 개의 값을 뽑아 낸 후 문제의 조건대로 연산하여 heapq.heappush() 메서드를 통해 배열에 추가시켰다.
• 스코빌 지수를 K 이상으로 만들 수 없는 경우는 연산을 지속하여 배열에 하나의 값이 남아도 K 미만일 경우이다.

• 채점 결과 정확도는 100%였으나 효율성 테스트에서 완전히 실패였다. 어떻게 하면 쓸데 없는 연산을 줄일 수 있을까 고민해본 결과, While문의 조건과 min() 함수를 사용하는 부분이 충분히 수정할 수 있다고 생각하여 수정을 하였다.

🙆‍♂️ 세 번째 풀이

import heapq


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

print(solution([1, 2, 3, 9, 10, 12], 7))

• 두 번째 풀이 처럼 굳이 min()함수를 사용할 필요가 없었다. 0번 인덱스로 값을 뽑아내면 얼마든지 가능했었다.
• 정확도, 효율성 모두 통과하였다.