자료구조 - 힙 (백준 11279)

수업시간에 배운 내용을 활용하여 백준 문제에 도전하였다.

배운대로 실행하여서 예제 테스트 케이스는 통과하였지만 바로 런타임 에러가 난 것을 볼 수 있었다.

이번에는 알고리즘의 에러였다

(신난다 !! 드디어 환경설정의 에러가 아닌 알고리즘 문제 해결 과정의 에러를 만나서 내심 기뻤다.)

에러의 원인은 런타임 에러 [Index Error].

어디서 인덱스 에러가 났을까를 구글링을 하였지만 많은 사람들이 heapq 라는 모듈을 사용하여 실제 내부 구현을 보기는 어려웠다.. (이때 내부구조를 구현하고 실행해본 것이 분명 도움이 되겠구나 라고 생각하였다.)

그래서 분명 맞게 하였는데 잘 모르겠어서 백준 질문 탭에서 도움을 요청하였다.

보아하니, 자식들의 인덱스를 정확히 처리하지 않았던 것이다.

나의 문제점을 정리하자면

1. pop 실행시 root Node를 제거 한 뒤 남아있는 리스트에 대해 heap 자료구조에 맞게 정렬을 할 경우 자식 노드들의 인덱스의 예외 처리를 정확히 처리해주지 않았음.

• root Node 제거 뒤 가장 하단 우측의 node를 root node로 바꿔주는데 여기서 만약 오른쪽 자식이 root Node로 갔다면 왼쪽 자식만 존재할텐데 이때 오른쪽 자식이 이미 없어졌는데 찾으려고 하니 인덱스 에러가 났음 (지금 생각해보니 당연히 날 수 밖에 없음 ,, )

나의 해결책

자식들의 인덱스 값과 힙 배열의 길이를 비교하여 만약 비교하려는 자식의 인덱스가 힙 배열의 길이보다 클 경우 무조건 break를 통해 탈출하려 했음

• 문제의 코드

if left_child_index > len(self.data)-1 or right_child_index > len(self.data)-1:

2. 이렇게 되버리면 왼쪽만 자식이 있을 경우 부모와 비교하여 자식이 더 클 경우 바꿔줘야 하지만 위 문제의 코드 때문에(자식 인덱스 값과 힙 배열 길이와 비교하여 자식 인덱스 값이 더 크므로) 바로 탈출하게 되어버린다.. 그러면 자식이 더 크다 하더라도 못바꿔주므로 이후 heap 배열이 꼬여버린다.

kwakws0627님의 해결책

3가지의 경우를 모두 나눠서 생각한다.

1. 왼쪽 자식도 없는 경우 (자식 아무도 없음)
2. 왼쪽 자식만 있는 경우 (자식 1개만 있음)
3. 왼쪽 오른쪽 둘 다 있는 경우 (자식 2개 모두 있음)

위를 참고하여 바꿔주니 모든 문제가 해결되었다.

            '''자식이 없는 경우'''
            if left_child_index == len(self.data):
                break
            '''왼쪽 자식만 있는 경우'''
            if left_child_index == len(self.data)-1:
                '''왼쪽 자식이 부모보다 더 클 경우 서로 switch'''
                if (self.data[now_index] < self.data[left_child_index]):
                    self.data[now_index], self.data[left_child_index] = self.data[left_child_index], self.data[now_index]
                else:
                    break
            elif (self.data[now_index] >= self.data[left_child_index]) and (self.data[now_index] >= self.data[right_child_index]): # 둘 다 있는 경우
            	break

소스코드

import sys

class maxHeap():

    def __init__(self): # 생성자
        self.data = list()

    def push(self, value): # 새로운 원소를 삽입하는 push
        self.data.append(value)
        now_index = len(self.data) - 1
        while(True): # 부모노드와 비교하며 자식노드가 부모 노드보다 크면 바꿔줌
            parent_index = (now_index - 1) // 2 # 부모 인덱스
            if (parent_index < 0): # 부모 노드 인덱스가 0보다 작다는 것은 원소가 1개인 것
                break


            if (self.data[now_index] <= self.data[parent_index]): # 부모노드가 자식 노드보다 큰 경우는 swap 없이 그대로
                break
            else: # 자식 node 가 부모 node보다 클 경우에만 swap
                self.data[now_index], self.data[parent_index] = self.data[parent_index], self.data[now_index]
                now_index = parent_index


    def pop(self): # Root Node를 제거하는 Pop
        now_index = len(self.data) - 1 # 최하단의 index
        # self.data[0], self.data[now_index] = self.data[now_index], self.data[0] # 최하단, 최우측의 node를 Root로 swap하여 변경
        self.data[0] = self.data[now_index]
        del self.data[now_index] # 기존 Root node 제거
        now_index = 0 # index 0으로 초기화

        while(True): # 자식 node 들과 비교하며 부모노드가 더 작을 경우 더 큰 자식노드와 바꿔줌
            left_child_index = now_index * 2 + 1 # 바로 아래 자식의 왼쪽 노드
            right_child_index = now_index * 2 + 2 # 바로 아래 자식의 오른쪽 노드
            if left_child_index >= len(self.data): # 자식의 오른쪽 노드의 인덱스 위치가 힙 전체 길이보다 크거나 같다면 탈출
                break
            elif len(self.data) < 3: # 길이가 2 이하인 경우 예외처리 해줌
                if self.data[now_index] >= self.data[left_child_index]:
                    break # root node 와 자식 node 를 비교하여 더 큰 값을 root에 설정
                else:
                    self.data[now_index], self.data[left_child_index] = self.data[left_child_index], self.data[now_index]
                    break # root 가 더 작으면 바꾼 후 탈출
            '''자식이 없는 경우'''
            if left_child_index == len(self.data):
                break
            '''왼쪽 자식만 있는 경우'''
            if left_child_index == len(self.data)-1:
                '''왼쪽 자식이 부모보다 더 클 경우 서로 switch'''
                if (self.data[now_index] < self.data[left_child_index]):
                    self.data[now_index], self.data[left_child_index] = self.data[left_child_index], self.data[now_index]
                else:
                    break
            elif (self.data[now_index] >= self.data[left_child_index]) and (self.data[now_index] >= self.data[right_child_index]): # 둘 다 있는 경우
                # 부모 now_index 가 왼쪽 자식보다 크고, 오른쪽 자식보다 클 경우 바로 탈출
                break
            else: # 부모 now_index 가 왼쪽 혹은 오른쪽 자식 둘중 하나보다 작을 경우
                if (self.data[left_child_index] > self.data[right_child_index]): # 왼쪽 자식보다 오른쪽 자식이 작을 경우
                    self.data[now_index], self.data[left_child_index] = self.data[left_child_index], self.data[now_index] # 왼쪽 자식과 부모 를 서로 바꾼다
                    now_index = left_child_index # 현재 index를 왼쪽 자식으로 바꾼다 (while문을 통해 계속 비교하기 위해)
                else: # 왼쪽 자식보다 오른쪽 자식이 클경우
                    self.data[now_index], self.data[right_child_index] = self.data[right_child_index], self.data[now_index] # 부모와 오른쪽 자식을 서로 바꾼다
                    now_index = right_child_index # 현재 인덱스를 오른쪽 자식으로 바꾼다


heap = maxHeap()

n = int(sys.stdin.readline())

command_lst = list()

for i in range(n):
    command_lst.append(int(sys.stdin.readline()))

for j in command_lst:
    if j == 0:
        if len(heap.data) < 1:
            print(0)
        else:
            print(heap.data[0])
            heap.pop()
    else:
        heap.push(j)