프로그래머스 Heap - 더맵게

Jamwon·2021년 9월 25일
0

알고리즘

목록 보기
18/18
post-thumbnail

문제링크

문제 유형자체가 heap유형으로 heap으로 푸는것이라고 알려주고 있다.

Heap

힙이란!!

최대값과 최솟값을 완전이진트리로 구현된 트리이다.
최대값과 최솟값을 빠르게 찾을때 사용된다.

힙은 Min Heap 과 Max Heap으로 구성되어있는데

Min Heap - 부모 노드의 값이 자식 노드 보다 항상 작다.
Max Heap - 부모 노드의 값이 자식 노드 보드 항상 크다.

heapq

파이썬에서 제공하는 Heap
heapq

heapq는 최소 합으로 정렬된다.

heapq.heappush(heap, key)

key값을 heap에 추가

heapq.heappop(heap)

heap에서 가장작은 원소 0번째 인덱스를 삭제하고 return 한다.

heapq.heapify(list)

list를 heap으로 변환해준다.

O(N)의 시간복잡도를 가진다.

문제 해결

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

    while len(scoville) >= 1:

        if len(scoville) == 1:
            if scoville[0] < K:
                return -1
            else:
                return answer
        least = heapq.heappop(scoville)

        if least >= K:
            print(answer)
            return answer
        least2 = heapq.heappop(scoville)
        add = least
        heapq.heappush(scoville, least + (least2 * 2))
        answer += 1

    return -1

문제를 이렇게 풀었다!

scoville를 heapify를 이용해서 최소힙으로 만들어준다음에 scoville의 길이가 1이상일때까지 while문을 돌렸다.

그리고 while문 내부에 scoville의 길이가 1이면 2개를 합칠 수 없기때문에 여기서 원소의 값이 K보다 작으면 -1를 return 크면 answer를 return 하였다 .

이 부분이 없으면 16번 test case가 계속 틀린다!!!

그리고 최소값이 K보다 작다면 2최소값을 공식에 따라 합해서 scoville에 추가하는것을 반복한다!!

그러면 정답!!!

최대값 최소값을 빠르게 찾고싶을때! HEAP !!

profile
한걸음씩 위로 자유롭게

0개의 댓글