[CLASS 3]백준 11279번, 1927번 - 최대 최소 힙

11279번 : 최대 힙

 

최대 힙을 구현하는 문제이다. 자료구조를 잘 이해하고 있다면 직접 구현할 수 있다.

 

나는 정말 열심히 최대 힙을 구현했는데 시간 초과에 걸렸다... 시간 제한이 매우 빡세다

 

그래서 갈아엎고 구글에서 최대 힙에 관해 검색한 뒤 따라 구현했는데도 틀렸다.

 

내 코드(틀렸습니다):

import sys
input = sys.stdin.readline

class maxHeap:
    def __init__(self):
        self.data = [None]

    def insert(self,item):
        self.data.append(item)
        i = len(self.data) - 1

        while i > 1:
            if self.data[i] > self.data[i//2]:
                self.data[i],self.data[i//2] = self.data[i//2],self.data[i]
                i //= 2
            else:
                break
    
    def remove(self):
        if len(self.data) > 1:
            self.data[1],self.data[-1] = self.data[-1],self.data[1]
            data = self.data.pop()
            self.maxHeapify(1)
        else:
            data = 0
        return data

    def maxHeapify(self,i):
        left = i * 2
        right = i * 2 + 1
        li = []

        if left < len(self.data) and self.data[i] < self.data[left]:
            li.append(left)
        if right < len(self.data) and self.data[i] < self.data[right]:
            li.append(right)
        
        if len(li):
            change = li[0]
            if len(li) == 2:
                change = max(li)
            self.data[i],self.data[change] = self.data[change],self.data[i]
            self.maxHeapify(change)

maxheap = maxHeap()
for _ in range(int(input())):
    req = int(input())
    if req:
        maxheap.insert(req)
    else:
        print(maxheap.remove())

 

도대체 왜 틀렸는지 아직도 도무지 모르겠다. 정말 모르겠다.

 

import sys
import heapq
input = sys.stdin.readline

heap = []

for _ in range(int(input())):
    req = int(input())
    if req:
        heapq.heappush(heap,-req)
    elif heap:
        print(-heapq.heappop(heap))
    else:
        print(0)

 

힙큐 모듈을 사용한다면 쉽게 해결할 수 있겠지만 내가 구현한게 어디서 틀렸는지 정말 모르겠다... 틀린 테스트케이스라도 보여주면 참 좋을텐데 백준은 이런 점에서 참 아쉽다.

 

1927번 : 최소 힙

 

최소 힙은 최대 힙에서 -를 붙인 형태로 사용하면 된다. 기존 heapq는 원래 최소 힙으로 구현되어 있으니 이것을 사용하려면 그냥 사용하면 된다.

 

import heapq
from sys import stdin
input = stdin.readline

minHeap = []
for _ in range(int(input())):
    req = int(input())
    if req:
        heapq.heappush(minHeap,req)
    elif minHeap:
        print(heapq.heappop(minHeap))
    else:
        print(0)