[Python]프로그래머스 - 더 맵게(level2)

문제출처 - https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게 | 프로그래머스

틀린 풀이1 - 런타임에러 + 시간초과

def solution(scoville, K):
    answer = 0

    while min(scoville) < K:
        scoville.sort()

        new_scoville = scoville[0] + scoville[1] * 2
        del scoville[0:2]
        scoville.append(new_scoville)

        answer += 1

    if max(scoville) < K:
        return -1

    return answer

매번 정렬하면서 젤 작은거랑 두번째로 작은거 섞어줌

인덱스처리가 안돼서 런타임에러도 나고 매번 정렬해줘서 시간초과도 남

 

 

틀린 풀이2(우선순위큐 사용) - 시간초과

from queue import PriorityQueue


def solution(scoville, K):
    answer = 0
    que = PriorityQueue(maxsize=len(scoville))

    for i in scoville:
        que.put(i)

    while True:
        # 길이가 1이 되었을때 예외처리
        if que.qsize() == 1:
            if que.get() < K:
                return -1

        first = que.get()
        second = que.get()
        new_scoville = first + second * 2
        que.put(new_scoville)

        if first >= K:
            break

        answer += 1

    return answer

이번엔 인덱스 예외처리도 해주고 우선순위큐를 사용했지만 시간초과..

 

 

성공한 풀이(힙 사용)

import heapq

def solution(scoville, K):
    answer = 0
    heap = []

    for i in scoville:
        heapq.heappush(heap, i)

    while heap[0] < K:

        # 예외처리
        if len(heap) == 1:
            if heap[0] < K:
                return -1
                
        heapq.heappush(heap, heapq.heappop(heap) + heapq.heappop(heap) * 2)

        answer += 1

    return answer

설명

 

이번엔 heapq 라이브러리를 활용해 풀었다. heapq 라이브러리는 우선순위큐 라이브러리와 함수 사용법이 조금씩 달랐다.

 

1. scoville 배열에 있는 모든 값을 힙에 넣어준다.

2. 힙에서 가장 작은 원소가 스코빌 지수보다 작으면 while문을 계속 돈다. 돌면서 힙에 원소가 1개 남은 경우 스코빌 지수보다 작으면 -1을 리턴해주고 아니면 힙에서 2개를 빼주고 1개를 추가한다.

 

만약 '힙에서 2개를 빼주고 1개를 추가한다.' 이 부분에서 나처럼

heapq.heappush(heap, heap[0] + heap[1] * 2)
heapq.heappop(heap)
heapq.heappop(heap)

이렇게 짠 사람이 있다면, 힙 삭제 원리를 다시 배우고 오자. 그러면 이 코드가 왜 틀렸는지 알게 될 것이다.