Lv2 [더 맵게]

[문제 설명]

- 맵기가 들어있는 배열 Scoville

- 최소 맵기 k

- Scoville 의 최소값이 k 이상이도록 주어진 식에 따라 섞어라.

 

[문제 풀이]

- Heap 공부

- 최소 힙으로 정리해서 두개 빼고 계산후 다시 넣기.

- 파이썬 heap 라이브러리가 있긴 한데 일단 내가 만들어 보기

 

[minHeap -수제작]

class MinHeap():

    def __init__(self):
        self.queue = []


    def insert(self,num):
        self.queue.append(num)
        lastIndex = len(self.queue)-1

        while lastIndex>=0:
            compareIndex = lastIndex // 2
            if compareIndex >= 0 and self.queue[lastIndex] < self.queue[compareIndex]:
                self.swap(lastIndex,compareIndex)
                lastIndex = compareIndex
            else:
                break

    def delete(self):
        lastIndex = len(self.queue)-1
        if lastIndex<0:
            return -1
        self.swap(lastIndex,0)
        minValue = self.queue.pop()
        self.heapSort(0)
        print(minValue)
        return minValue

    def heapSort(self,i):
        leftIndex = i*2+1
        rightIndex = i*2+2
        minIndex = i

        if leftIndex <=len(self.queue)-1 and self.queue[minIndex] > self.queue[leftIndex]:
            minIndex = leftIndex
        if rightIndex <=len(self.queue)-1 and self.queue[minIndex] > self.queue[rightIndex]:
            minIndex = rightIndex

        if minIndex != i:
            self.swap(i, minIndex)
            self.heapSort(minIndex)

    def swap(self,lastIndex,compareIndex):
        self.queue[lastIndex], self.queue[compareIndex] = self.queue[compareIndex], self.queue[lastIndex]

이거로 하면 시간초과 뜨니까 라이브러리 사용하자.(구현에 목적, 후에 누가 힙 구현 할줄 아냐고 물어보면 이거 보여주자)

import heapq 해서쓰자.

  -heappush(heap,item): heap 으로 push

  -heappop(heap): heap의 root pop

  -heappushpop(heap,item): push,pop을 한번에 하는건데 따로 하는거보다 효율적임

  -heapreplace(heap,item): pop, push순서로 함.

  -heapify(list): list를 Heap정렬 해줌

 

- 최소값 pop 이후에 배열에 아무것도 남아있지 않으면 -1을 리턴 해줘야 한다.