[파이썬]백준 11279 최대 힙

링크

백준 11279 최대 힙

오늘 싸피에서 힙을 배워서 힙 문제를 풀어봤다.
분명 작년 이맘때 쯤 학교에서 자료구조 수업을 수강할 때 배웠을텐데.. 왜 그 땐 이해가 안됐을까..?
지금 다시 들으니 이해가 너무 잘돼서 당황스러울 정도다.
아마, 마음가짐의 차이인 것 같다. 그땐, 학위만 필요해서 꾸역꾸역 수업을 들었을 때고 지금은 정말 하고싶어서 공부하니 이해가 잘되는 것 같다.

힙을 직접 구현하는게 의미가 있을 것 같아 직접 구현했으나 틀렸다. 일단 코드는 올리지만 추후에(되도록 내일) 고쳐서 수정하도록 하겠다.

결국 내장함수를 사용해서 풀었는데 내장함수를 사용하면 굉장히 쉬운 문제이다.
단, 파이썬의 경우 input()을 사용하면 시간초과가 나고 반드시 sys.stdin.readline()을 사용해야한다. 아마 문제에서 값을 하나씩 줘서 둘의 시간차이가 많이 나는 것 같다.

오답 코드 (맥스힙 구현) (수정 예정)

class MaxHeap:

    def __init__(self):
        self.data = [None] #힙에선 0번 인덱스 사용 X

    def Hpush(self, item):
        self.data.append(item)

        lastIdx = len(self.data) - 1
        child = lastIdx
        parent = lastIdx // 2

        while parent != 0: # 부모가 root를 넘어가지 않음
            if  self.data[child] > self.data[parent]: # 자식이 부모보다 크면
                # 부모와 자식 바꿔줌
                self.data[child], self.data[parent] = self.data[parent], self.data[child]
                child = parent #자식은 기존의 부모로 해서 트리를 올라감
                parent = child // 2 #바꿔준 자식의 부모를 다시 할당
            else:
                break

    def Hpop(self):
        if len(self.data) > 1: #힙에 데이터가 있는 경우
            #가장 끝에 값과 루트를 바꿔줌 (힙은 트리의 가장 마지막 인덱스에서만 삽입 삭제가 가능하기 때문)
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            value = self.data.pop() #가장 마지막 값으로 바꿔준 기존의 루트를 뽑아냄
            self.maxHeapify(1) #재정렬
        else: # 힙에 아무것도 없을 경우
            value = 0
        return value

    def maxHeapify(self, root): # 인자로 받는 root 부터 root의 값과 자식들을 비교하며 재정렬
        l_child = 2 * root
        r_child = (2 * root) + 1
        max_vertex = root #큰 값을 담을 변수, root로 초기화 (root부터 시작이니까)
        #왼쪽 자식이 존재하고 root보다 왼쪽 자식이 더 클경우
        if l_child < len(self.data) and self.data[root] < self.data[l_child]:
            max_vertex = l_child #최대값 변수에 왼쪽 자식 넣어줌
        #왼쪽이 있더라도 오른쪽이 있으면 오른쪽으로 바꿔줌
        if r_child < len(self.data) and self.data[root] < self.data[r_child]:
            max_vertex = r_child
        #만약 root보다 자식이 더 커서 max_vertext가 바뀌었으면 둘의 위치를 바꿔줌
        if max_vertex != root:
            self.data[root], self.data[max_vertex] = self.data[max_vertex], self.data[root]
            self.maxHeapify(max_vertex) #새로운 root부터 다시 함수 호출해서 정렬

import sys

N = int(sys.stdin.readline())
heap = MaxHeap()
for _ in range(N):
    num = int(sys.stdin.readline())
    if num == 0:
        value = heap.Hpop()
        print(value)
    else:
        heap.Hpush(num)

정답 코드

import sys

N = int(sys.stdin.readline())
heap = MaxHeap()
for _ in range(N):
    num = int(sys.stdin.readline())
    if num == 0:
        value = heap.Hpop()
        print(value)
    else:
        heap.Hpush(num)

알게된 것👨‍💻

• 공부는 마음가짐