프로그래머스 - 더 맵게 (heap) - Python

안녕하세요. 

부족한 개발 실력이지만, 꾸준하게 공부한 기록을 남겨놓기 위해서 제가 풀이한 알고리즘 문제를 공유하려고 합니다. 

저와 같은 초보 개발자분들에게 많은 도움이 되었으면 좋겠습니다 ! 

 

728x90

오늘 풀어본 문제는 프로그래머스에 있는 '더 맵게(heap)' 문제입니다 .

 

heap 자료구조를 사용하는 문제인데, 저는 처음에 그냥 list를 사용해서 문제를 풀어보았습니다.

 

def solution(scoville, K):
    answer = 0

    scoville.sort()
    if scoville[0] >= K: return answer

    while scoville[0] < K:
        if len(scoville) == 1:
            answer = -1
            break

        min_scov1 = scoville.pop(0)
        min_scov2 = scoville.pop(0)

        scov = min_scov1 + (min_scov2 * 2)
        scoville.insert(0, scov)
        scoville.sort()

        if scoville[0] >= K :
            answer += 1
            break
        else:
            answer += 1

    return answer

 

그 결과 테스트 문제는 다 통과했지만, 효율성 측면에서 런타임 에러가 발생한 것을 확인할 수 있었습니다.

그래서 heapq를 사용해서 문제를 다시 풀어보았습니다. 

 

import heapq

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

    if scoville[0] >= K:
        return answer

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

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

	return answer

 

그 결과 효율성 측면에서도 통과할 수 있었습니다.

list를 이용해서 pop, push를 하는게 heapq를 사용하는 것보다 느리다는 것은 알고 있었는데, 정확한 차이점에 대해서는 잘 모르겠더라구요 ㅠㅠ 

그래서 python에서 list와 heapq를 사용하는 측면에서 어떤 점이 다른지 조금 더 공부한 후에, 블로그에 정리해서 올려보도록 하겠습니다 ㅎㅎ