Programmers 코딩 테스트 연습 힙(Heap) 더 맵게 정답.

정렬과 해시, 힙, 스택, 큐는

 

시간 복잡도 개념에 있어서 익숙해 지는데 매우 중요한 문제들로 구성되어 있는 것 같다.

 

여러번 풀어서 반복 숙달하자.

 

이런 류의 정렬된 값을 계속 푸시 & 팝 해야 하는 경우는 우선순위 큐를 쓰는 것이 유리하고

 

리스트를 이용한 우선순위 큐는 파이썬의 heapq를 이용해서 만든다.

 

(heap은 우선순위 큐를 구현하기 위한 자료구조이다.)

 

PrioritiyQueue를 이용해서 만드는 방법도 있지만, 이는 (우선순위, 데이터)의 형태로 사용해야 하기 때문에

 

이런 문제를 풀기에 있어서는 귀찮다.

 

이 heapq에서 지원하는 heap은 minheap이다.

 

이 heapq를 통해 maxheap를 구성하기 위해서는 -를 넣어서 push해주고 다시 -를 붙여 pop해주는 약간의 번거로움이 존재한다. 내부적으로 maxheap를 구현할 수 있는 방법이 존재하지 않기 때문이다.

 

힙을 구성하는데 걸리는 시간복잡도는 O(nlogn)

 

삽입과 삭제에 걸리는 시간은 O(logn)이기 때문에,

 

정렬된 자료를 계속 push pop 하는 부분에 있어 매우 유용한 것이다!!

 

import heapq


def solution(scoville, k):
    heap = []
    for num in scoville:
        heapq.heappush(heap, num)
    mix_cnt = 0
    while heap[0] < k:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + heapq.heappop(heap) * 2)
            print("몇번 섞었나요?  : " + str(mix_cnt) + " 섞은 후의 값은...? : ")
            str(heap[0])
        except IndexError:
        #인덱스 예외처리로 귀찮은 if문 생성 해결
            return -1
        mix_cnt += 1
    return mix_cnt

 

 

이 문제는 input이 정렬되어 있어 착각을 불러일으킬 수 있지만,

중간의 연산 결과를 push 했을 때 꼭 앞에만 존재하는 것이 아니라

뒤로 갈 수 있기 때문에 priority queue를 사용해야 한다는 사실을 잊지 말아야 한다.

 

이 문제의 경우 시간 복잡도는 O(nlogn)이다. (정렬이 가장 시간을 잡아먹는 연산.