[BOJ] Python 백준 5639번 이진 검색 트리 실버 1

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

5639번: 이진 검색 트리

 

문제 풀이

---

전형적으로 이진 트리(Binary Tree)와 트리 순회(Tree Traversal)에 대한 문제다.

 

만약 이진 트리에 대해 처음 듣거나 익숙하지 않은 사람은 이전 포스팅을 참고하여 이해하고 오는 것이 좋을 것 같다.

 

https://khsung0.tistory.com/24

[자료구조] 트리(Tree) 이진 트리(Binary Tree) 트리 순회 (Tree Traversal) (Python)

 

문제는 전위 순회한 결과가 주어지고 이를 후위 순회한 결과를 출력하면 된다.

 

알고리즘 외적으로도 고려해야 할 부분이 많아서 상당히 골치 아팠던 문제기도 하다.

 

처음 생각한 풀이법은 노드의 수는 10,000개 이하고 전위 순회의 결과가 입력으로 주어지니 전위 순회 순서대로 트리에 삽입하여 완성된 트리를 후위 순회하여 출력하는 방식을 생각했었다.

 

하지만 생각치 못하게 시간 초과와 메모리 초과가 떠서 틀렸었다.

 

불합격 이미지

 

다음은 불합격한 코드이다.

 

import sys
sys.setrecursionlimit(10**6)

binary_tree={}        #이진 트리를 위한 딕셔너리 선언
while True:
    try:
        num=int(input())
        if len(binary_tree)==0:        #빈 트리일 때
            root=num                   #루트로 설정
            binary_tree[root]=['*','*']
        else:
            curr=root
            while True:
                #왼쪽 서브 트리일 때
                if num<curr:
                    #왼쪽 노드가 없을 때
                    if binary_tree[curr][0]=='*':
                        binary_tree[curr][0]=num
                        binary_tree[num]=['*','*']
                        break
                    #왼쪽 자식 노드로 이동
                    else:
                        curr=binary_tree[curr][0]
                #오른쪽 서브 트리일 때
                else:
                    #오른쪽 노드가 없을 때
                    if binary_tree[curr][1]=='*':
                        binary_tree[curr][1]=num
                        binary_tree[num]=['*','*']
                        break
                    #오른쪽 자식 노드로 이동
                    else:
                        curr=binary_tree[curr][1]
    except:
        break

def postorder(curr):
    #왼쪽 자식 노드로 이동
    if binary_tree[curr][0]!='*':
        postorder(binary_tree[curr][0])
    #오른쪽 자식 노드로 이동
    if binary_tree[curr][1]!='*':
        postorder(binary_tree[curr][1])
    #현재 노드 출력
    print(curr)

postorder(root)

 

2번째 줄은 파이썬에서 기본 재귀 깊이 제한이 1000이기 때문에 1000000으로 세팅하는 코드이다.

 

이 때문에 런타임 에러(Recursion Error)가 뜬 것이다.

 

또한 입력받는 부분에서 어디까지 받는다는 제한이 없으므로 try except 구문을 사용하여 예외가 발생하기 전까지 입력을 받고 트리에 추가하는 방식으로 하였다.

 

예외가 발생하면 그대로 트리를 후위 순회하여 출력했는데 불합격한 것을 보니 다른 방식을 생각해야 했다.

 

고민하던 중에 전위 순회는 현재 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순으로 탐색하고 후위 순회는 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 현재 노드 순으로 탐색하기 때문에 현재 노드를 출력하는 타이밍을 조절해야겠다는 생각이 들었고 현재 노드보다 작은 숫자는 왼쪽 서브 트리, 큰 숫자는 오른쪽 서브 트리로 구분 지을 수 있겠다는 생각이 들었다.

 

따라서 리스트를 기준으로 첫 번째 원소는 현재 노드라 마지막에 출력하고 현재 노드보다 작은 원소들의 리스트는 왼쪽 서브 트리로 여겨 재귀 호출, 큰 원소들의 리스트는 오른쪽 서브 트리로 여겨 재귀 호출하면 차례대로 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 현재 노드 순으로 출력될 것이라 생각했고 역시 통과했다.

 

다음은 통과한 전체 코드이다.

 

import sys
sys.setrecursionlimit(10**6)

#입력받을 원소 리스트
num_list=[]
while True:
    try:
        num=int(input())
        num_list.append(num)
    except:
        break

def postorder(left,right):
    #순서 역전시 종료
    if left>right:
        return
    else:
        mid=right+1        #분할 기준
        for i in range(left+1,right+1):
            #해당 원소가 현재 노드보다 크다면 그 전까지는 왼쪽 서브 트리,
            #해당 원소 이후는 오른쪽 서브 트리이다.
            if num_list[left]<num_list[i]:
                mid=i
                break
        postorder(left+1,mid-1)
        postorder(mid,right)
        print(num_list[left])

postorder(0,len(num_list)-1)

 

트리 생성이 아닌 단순히 리스트에 원소를 입력 받으므로 입력 받는 부분은 전보다 더 간단해졌다.

 

시작은 전체 리스트의 길이부터 시작하고 가장 첫 번째 원소는 현재 노드, 그 이후부터 반복문을 돌면서 현재 노드보다 큰 원소가 있다면 그 전까지는 왼쪽 서브 트리, 큰 원소부터 이후는 오른쪽 서브 트리로 구분지어 재귀호출한다.

 

만약 큰 원소가 없을 경우를 대비해 mid=right+1을 함으로써 없으면 현재 노드를 제외한 나머지를 왼쪽 서브 트리로 보내고 두 번째 호출하는 재귀 함수는 순서가 역전되어 종료되도록 구현하였다.

 

결과 화면

 

인덱스를 접근하고 관리하는 방법에서 다소 헷갈리는 부분이 있고 알고리즘 외적으로도 재귀 깊이를 변경한다든지 입력받는데 처리해줘야 하는 부분이 있는 문제였다.

 

또한 해당 코드를 PyPy3로 제출하면 메모리 초과가 뜬다.

 

PyPy3가 Python3보다 연산이 빠르기에 안전하게 하기 위해 PyPy3로 먼저 제출했었는데 자료를 찾아보니 PyPy3는 최대 재귀 깊이는 제한이 없으나 10만 단위 이상으로 들어가면 Stack Overflow가 발생하여 재귀에 약하다는 정보를 얻을 수 있었다.

 

따라서 시간 초과가 뜬다면 PyPy3로, 재귀를 사용하여 메모리 초과가 뜬다면 Python3으로 제출해야한다는 지식을 알게 되었다.