백준 11279번, 1927번 - 최대, 최소 힙

 

11279번 문제는 최대 힙, 1927번 문제는 최소 힙을 이용하여 각각 최댓값, 최솟값을 구하는 문제이다. 두 문제 모두 등호만 다를 뿐 코드는 같기 때문에, 더 어려울 수 있는 최소 힙을 풀겠다. 그전에 힙에 대해 알아보자.

 

힙이란, 우선순위 큐를 위한 자료구조이자, 다른 알고리즘에 비해 최댓값, 최솟값을 빠르게 구하게 해준다. 또한 힙은 반 정렬 상태이다. 처음에 우선순위 큐와 힙에 대해서 혼동이 왔었다. 내가 알던 큐는 처음에 들어온 것이 제일 먼저 나가는 FIFO형태였는데, 우선순위에 따라 먼저 나간다는 개념이 낯설었다.

 

힙은 우선순위 큐를 구현하기 위한 도구(?)이고, 또한 힙은 반 정렬 상태라는 것을 알고 나니 이해가 됐다. 반 정렬 상태라는 건 트리안의 모든 수가 정렬이 되어있는 것이 아니고 어느 정도만 정렬이 되어있다는 것이다. 밑의 그림은 힙에 값을 삽입하는 과정이다. 배열의 마지막에 붙여준 뒤에 부모 노드로 계속 올라가면서, 본인보다 작으면 서로 교체되는 식으로 진행이 된다. 그러면, 루트에는 언제나 가장 큰 (혹은 작은) 값이 올 것이다. 

 

 

반대로, 삭제하는 과정은 루트 노드를 삭제한 뒤, 배열의 가장 마지막 원소를 루트에 넣어주고, 자식 노드들을 거쳐가면서 갱신해준다. 삽입과 삭제의 과정은 거의 비슷하다고 할 수 있다. 

부모 노드의 인덱스는 자식의 인덱스를 2로 나눈 값이고, 자식 노드의 인덱스는 left child인 경우 부모 노드의 인덱스 * 2, right child인 경우 부모 노드의 인덱스 * 2 + 1 임을 이용하면 쉽게 문제를 풀 수 있다.

 

##함수 선언 부분
import sys
##변수 선언 부분
min_heap = []
cnt = 0
##메인 함수 부분
if __name__ == "__main__":
    N = int(sys.stdin.readline())
    min_heap = [-1] *100010
    for i in range(N):
        command = int(sys.stdin.readline())
        if command == 0:
            if cnt == 0: #들어있는 것이 없으면,
                print(0) #0출력
            else:
                print(min_heap[1])
                min_heap[1] = min_heap[cnt]
                min_heap[cnt] = -1 #pop후 저장
                cnt -= 1
                index = 1
                while index*2 <= cnt:
                    if (index*2+1) > cnt: #left child만 있는 경우에는
                        if min_heap[index] > min_heap[index*2]: #left child값보다 크면,
                            tmp = min_heap[index] #교환
                            min_heap[index] = min_heap[index * 2]
                            min_heap[index * 2] = tmp
                            index *= 2
                        else: 
                            break
                    elif min_heap[index] > min(min_heap[index*2],min_heap[index*2+1]): #자식 노드의 최솟값보다 크면,
                        if min_heap[index*2] < min_heap[index*2+1]: #left child가 더 작으면,
                            tmp = min_heap[index] #교체
                            min_heap[index] = min_heap[index*2]
                            min_heap[index*2] = tmp
                            index *= 2
                        else:
                            tmp = min_heap[index]
                            min_heap[index] = min_heap[index*2+1]
                            min_heap[index*2+1] = tmp
                            index = index * 2 + 1
                    else:
                        break

        else:
            cnt += 1 #원소 개수 증가
            min_heap[cnt] = command 
            index = cnt
            while index > 1: #index부터 1보다 작아질 떄 까지 2로 나누어서 부모 노드로 이동
                if min_heap[index] < min_heap[index//2]: #부모모다 작으면
                    tmp = min_heap[index] #교체
                    min_heap[index] = min_heap[index//2]
                    min_heap[index//2] = tmp
                index //= 2

input()을 사용해서 시간 초과가 떴다. 앞으로 시간 초과가 나오면, sys.stdin.readline()을 먼저 의심해봐야겠다.