[백준/Python] 11279번 - 최대 힙

 

문제

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

 

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

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

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

 

 

입력

 

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.

 

다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.

 

만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다.

 

입력되는 자연수는 2^31보다 작다.

 

 

출력

 

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

 

풀이

 

자료구조 중 최대 힙은 완전 이진 트리(Complete Binary Tree)구조 이며 부모노드가 자식노드들보다 크다.

 

완전 이진트리의 구조이기 때문에 [부모노드의 index]*2가 왼쪽 자식 노드의 index값이며 [부모노드의 index]*2+1는 오른쪽 자식 노드의 index값이다.

 

위의 문제에서 최대값을 빠르게 구하기 위해서는 이와 같은 최대 힙 자료구조를 이용해서 풀었다.

​

1. 최대 힙에서 노드의 삽입 시 => 완전 이진 트리의 마지막 index 다음 index에 삽입하고 부모노드와 값을 비교한 뒤 더 크면 교환하고, 작으면 그대로 둔다.

​

2. 최대 힙에서 노드의 삭제 시 => 노드를 삭제하고 자식 중 마지막 index를 삭제한 노드의 index 위치로 옮긴다. 그리고 왼쪽 자식 노드와 오른쪽 자식 노드 중 큰 값과 값을 비교하고 자식 노드가 더 크면 위치를 교환한다. 이 과정을 반복하며 자리를 찾아간다.

 

 

Code

 

 

import sys
input=sys.stdin.readline
idx=0
lst=[0]*2000001
for tc in range(int(input())):
    # print(lst)
    n=int(input())
    if n:
        idx += 1
        lst[idx]=n
        ca_idx=idx
        while ca_idx>1:
            ca_idx_2=ca_idx//2
            if lst[ca_idx_2]>lst[ca_idx]:
                break
            else:
                lst[ca_idx_2],lst[ca_idx]=lst[ca_idx],lst[ca_idx_2]
                ca_idx=ca_idx//2
    else :
        print(lst[1])
        lst[1]=lst[idx]
        lst[idx]=0
        if idx:
            idx-=1
            ca_idx=1
            while True:
                if lst[ca_idx*2]:
                    if lst[ca_idx*2]>lst[ca_idx*2+1]:
                        if lst[ca_idx]>lst[ca_idx*2]:
                            break
                        else:
                            lst[ca_idx],lst[ca_idx*2]=lst[ca_idx*2],lst[ca_idx]
                            ca_idx*=2
                    else:
                        if lst[ca_idx]>lst[ca_idx*2+1]:
                            break
                        else:
                            lst[ca_idx], lst[ca_idx * 2+1] = lst[ca_idx * 2+1], lst[ca_idx]
                            ca_idx = ca_idx*2+1

                else:
                    break

 

---

 

자료구조도 한번 다시 봐둬야 하는데...