[프로그래머스] 힙 1. 더 맵게

문제

출처: 프로그래머스

---

풀이

힙의 개념이 가물가물해서 먼저 힙이 무엇이었는지 찾아보았다.

힙은 완전이진트리의 일종으로 최댓값, 최솟값을 추출하기 쉬운 자료구조였다.

그냥 리스트로 처리하고 매번 정렬하는 방법도 생각해보았으나 일단 힙 먼저 사용해보기로 했다.

파이썬 모듈이 존재할 것 같아 찾아보고 적용하였다.

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while(scoville[0] < K):
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        heapq.heappush(scoville, first + second * 2)
        answer += 1
    
    return answer

여기서 시간복잡도는 다음과 같다.

heap.heapify(heapname)	리스트를 힙으로 변경	O(n)
heap.heappop(heapname)	0번째 요소 삭제	O(logn)
heap.heappush(heapname, number)	number 요소 추가	O(logn)

 

코드의 빅오 시간복잡도는 O(logn * answer) 혹은 O(n)중 큰 쪽일 듯 하다.

걱정했던 효율성 테스트는 통과했는데 런타임 에러가 발생했다. 문제를 다시 읽어보니 불가능하면 -1을 반환하라는 조건이 있어 수정 후 통과했다.

import heapq

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

기존에 생각했던 정렬로 푸는 방법은 시간이 얼마나 걸릴지 궁금해 다른 사람의 코드를 보았다.

거의 전부 나와 비슷한 풀이로 풀어서 인터넷에 검색해보았는데, sort로 풀면 효율성테스트를 통과하지 못한다고 한다.

sort가 O(nlogn)이고 answer만큼 반복해서 그런 듯 하다.

 

찾는 중에 힙을 사용하지 않고 queue로 더 적은 시간으로 푼 사람이 있다 하여 글을 가져와보았다.

코드들을 보니 다들 import heapq를 하셨는데 저는 heap을 몰라서..ㅎㅎ queue만 써서 풀었는데도 시간이 heap을 쓴 풀이의 절반 정도 걸리네요. 저는 섞어서 나온 새로운 값, mix들을 별도의 queue에 넣었는데 이게 가장 큰 요인같네요. 나중에 나온 mix값이 먼저 나온 것보다 클 수밖에 없어서 섞는 순서대로 queue에 넣어주면 크기 순서를 신경 쓸 필요가 없어요. 그냥 popleft로 꺼내면 무조건 mix값의 최소입니다

새 음식은 별도의 queue를 사용하고 기존 scoville 배열값과는 if문을 사용해 비교하지 않았을까 싶다.

이게 가장 효율적인 듯!

 

 

출처:

gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

www.daleseo.com/python-heapq/