[WEEK02/DAY03] 백준 문제 : 최대 힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

 

문제 해석 :

자료구조 '최대 힙'을 이용하여 다음과 같은 기능을 하는 프로그램을 만드는 문제다.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

 

접근 :

우선순위 큐를 사용하는 문제이다.

우선순위 큐가 일반 큐와 다른 점은,

일반 큐의 경우 선입선출(First In First Out)을 해야 하지만

우선순위 큐는 내가 매긴 우선순위에 따라 출력을 해야 한다는 점이 다르다.

 

이 문제의 경우 배열에서 가장 큰 값을 출력해야 한다.

단순히 리스트 자료구조를 사용하면 매번 탐색에 시간복잡도 O(N)이 필요하다.

더군다나 해당 값을 출력하면서 리스트에서 제거한다면 추가로 O(N)이 더 걸린다.

아무래도 제한시간 내에 최대 10만 번의 연산을 해내기엔 어려울 것이다.

 

그래서 힙 구조를 사용해야 한다.

 

힙은 완전 이진 트리의 형태를 띠고 있다.

완전 이진 트리는 부모(parent)요소가 자식(children)요소를 두 개 까지만 가지는 트리이며, 위에서 아래로, 왼쪽에서부터 오른쪽으로 index 번호를 매긴다고 했을 때 꽉 채워져 있다는 특징이 있다.

힙 구조는 여기서 '부모 레벨에 위치한 노드들의 값이 자식레벨의 노드들의 값보다 크도록' 해주면 된다.

형제(sibling)간에는 크기를 비교하지 않아도 된다.

힙 정렬된 완전 이진 트리의 모습 - 반드시 오른쪽 자식이 있어야 하는 건 아니다.

힙 구조를 사용하면 우선순위 큐 구현에 시간적으로 유리하다.

 

삽입할때는 제일 마지막 index에 삽입해서, 부모 노드와 비교하여 자식이 부모보다 크면 바꾸는 일을 반복한다. 그러면 힙 구조를 유지할 수 있다. 이는 O(logN)의 시간복잡도를 가지고 있다.

최대값인 루트 노드를 출력하고 삭제할 때에도, 가장 마지막 노드를 루트 노드로 올린 다음에 자식과 비교하여 부모가 더 작으면 바꿔주는 일을 반복하면 힙 구조를 유지할 수 있다. 이 역시 O(logN)의 시간복잡도를 가지고 있다.

 

자, 그럼 문제 해석은 되었고, 이제 구현을 해야 하는데...

 

 

구현 :

사실 python에서 제공하는 내장모듈인 heapq를 이용하면 손쉽게 풀어낼 수 있는 문제다.

하지만 나는 이렇게 자료구조 문제를 처음 대면할 때... 모듈을 쓰지 않고 직접 구현하고 싶어하는 욕구가 있다.

그래야 스스로 이해가 되니까...

물론 한 번 구현하고 나면 그 다음부터는 내장 모듈을 쓴다.

시간적으로도 직접 구현한 코드보다 내장 모듈의 속도가 훨씬 빠르다. (아무래도 내장모듈 함수들의 경우 최적화가 되어있기 때문)

 

아무튼 그래서 직접 '최대 힙'을 만들어서 풀었다.

 

기본 개념은 이진 트리인데, 원래는 부모 노드에 left와 right 값을 줘서 자식 노드들과 연결을 해줘야 하는게 트리 아닌가.

하지만 완전 이진 트리는 index값을 활용하여 배열처럼 사용할수가 있다.

이진트리가 꽉 차있기 때문에, 부모의 left 노드는 index*2를 하면 찾을 수 있다. right 노드 역시 index*2 + 1을 하면 된다.

자식 노드에서 부모 노드를 찾을때도, 2로 나눈 나머지가 0이면 왼쪽에 달려 있는 것이고, 1이면 오른쪽에 달려 있는 것이다.

위 그림을 참고하면 더 명확히 이해가 될 것이다.

 

아직 트리 구조에 익숙하지 않아서 구현이 쉽지 않았지만, 언젠가는 정복해야 할 구조니까 열심히 구현해 봤다.

다른 트리들은 더 힘들다던데...

 

 

 

아래는 내가 제출한 정답 코드이다.

import sys

class Node:
    def __init__(self, value:int) -> None:
        self.idx = 1
        self.value = value

class Heap:
    def __init__(self, capacity:int = 104800) -> None:
        self.arr = [None]*capacity
        self.end = 1

    def insert(self, value:int) -> None:
        # root가 없을 때. 처음 만든 힙일때.
        if self.arr[1] == None:
            self.arr[1] = Node(value)
            self.end += 1
        else:
            # 힙 트리의 맨 마지막에 노드 삽입
            current_node = Node(value)
            self.arr[self.end] = current_node
            current_node.idx = self.end
            self.end += 1

            # 막내 노드 힙하게 만들어주기
            parent = self.arr[current_node.idx//2]
            while parent.value < current_node.value:
                x = parent.idx
                parent.idx = current_node.idx
                current_node.idx = x
                self.arr[parent.idx] = parent
                self.arr[current_node.idx] = current_node

                if current_node.idx == 1:
                    break
                else:
                    parent = self.arr[x//2]

    def pop(self) -> int:
        # 루트가 없는지 확인
        if self.end == 1:
            return 0

        # 루트 노드에 막내 노드 넣어주기
        value = self.arr[1].value

        rear = self.arr[self.end-1]
        rear.idx = 1
        self.arr[1] = rear

        self.end -= 1
        self.arr[self.end] = None

        # 올라간 막내 노드 힙하게 제자리 찾아주기
        if self.arr[1] != None:
            current_node = self.arr[1]

            while True:
                left = self.arr[current_node.idx*2]
                right = self.arr[current_node.idx*2+1]

                if right == None:
                    if left == None:
                        break
                    else: child = left
                else:
                    if left.value >= right.value: child = left
                    else: child = right

                if child.value > current_node.value:
                    x = child.idx
                    child.idx = current_node.idx
                    current_node.idx = x
                    self.arr[child.idx] = child
                    self.arr[current_node.idx] = current_node
                else: break

        return value



def main():
    n = int(input())
    x = [0]*n
    for i in range(n):
        x[i] = int(sys.stdin.readline().strip())
    
    heap = Heap()
    for i in range(n):
        if x[i] == 0:
            print(heap.pop())
        else:
            heap.insert(x[i])

main()