[백준] 5639번 : 이진검색트리 (파이썬)

재귀 문제

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

 

 

풀이코드  (실패, 시간초과)

# 무한입력을 위해 try - except 추가
# 25%에서 시간초과 코드 

import sys
sys.setrecursionlimit(10**9)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def insert(root, data):
    if root == None:
        return Node(data)
    else:
        if root.data > data:  # 왼쪽
            root.left = insert(root.left, data)
        else:
            root.right = insert(root.right, data)
    return root

        
def postOrder(root):
    if root == None: return 
    else:
        postOrder(root.left)
        postOrder(root.right)
        print(root.data)

node = None
while True:
    try:
        n = int(sys.stdin.readline())
        node = insert(node, n)
    except:
        postOrder(node)
        break

 

👩🏻‍💻 위의 코드

입력으로 트리를 '전위 순회'한 결과를 주었음에도 불구하고, 이러한 정보를 써먹지 않은 코드이다. 

즉, 전위 순회한 정보를 문제를 해결하는 데에 사용하지 않고, BST의 입력으로 일반 랜덤한 값을 받는 것과 동일하게 코드를 짰다.

이에 BST를 만드는 데에 필요한, tree의 불필요한 insert가 반복되었다.

 

 

💡 풀이코드 (성공)

import sys
from itertools import zip_longest
sys.setrecursionlimit(10**9)


def post(start, end):
    print(start, end)
    if start > end: return 

    mid = end + 1
    for i in range(start + 1, end + 1):
        if arr[start] < arr[i]:
            mid = i
            break 
    post(start + 1, mid - 1) # 왼
    post(mid, end) # 오
    print(arr[start]) # 루트 출력
        

arr = []
# 입력으로 몇 개를 줄지 사전에 정의되지 않기 때문에 파이썬에서 EOF Error가 나는 것을 활용
while True:
    try:
        n = int(sys.stdin.readline())
        arr.append(n)
    except:
        break
post(0, len(arr) - 1)

 

👩🏻‍💻 위의 코드

전위순회 결과 : 50 30 24 5 28 45 98 52 60 (루트 -> 왼 -> 오)

후위순회 결과 : 5 28 24 45 30 60 52 98 50 (왼 -> 오 -> 루트)

• base condition : 재귀를 돌며 start가 end보다 크다면 리턴한다.
• for문 로직
  • if문에 걸리지 않아 mid값이 초기화되지 않을 것을 고려하여 사전에 mid를 end + 1로 초기화해준다.
    end + 1로 초기화해주는 이유는 post(start + 1, mid - 1)에서 현재 start보다 큰 값이 없을 경우 post(start + 1, end)로 범위를 좁혀 재귀를 돌기 위함이다.
    ex) arr = [50 30 24 5 28 45] -> start = 0, mid = 6 => post(1, 5)로 start의 범위를 좁혀 탐색 
• 다음은 순서대로 후위순회를 하는 코드이다. (왼쪽 tree -> 오른쪽 tree -> 루트 출력)

    post(start + 1, mid - 1) # 왼
    post(mid, end) # 오
    print(arr[start]) # 루트 출력

 

• 다음은 코드에서 실행하는 재귀 호출을 그림으로 나타내보았다.

 

 

참고문헌

https://yoons-development-space.tistory.com/5

백준 5639 이진검색트리 파이썬

https://sinclairstudio.tistory.com/152

[백준] 5639 이진검색트리 in Python : tree 전위순회의 특성을 이용한 풀이 + EOF를 이용해서 입력받기

https://ku-hug.tistory.com/132

[Python/파이썬] 백준 5639번: 이진 검색 트리