[CLASS 4]백준 5639번 - 이진 검색 트리

5639번 : 이진 검색 트리

 

트리를 그냥 주는게 아니라 전위 순회한 결괏값을 주기 때문에 처음에 나는 먼저 트리를 구현->후위 순회를 하는 코드를 작성했다.

 

내 코드(python 시간 초과):

# dawitblog.tistory.com
import sys
sys.setrecursionlimit(20000)
input = sys.stdin.readline

# 노드
class Node:
    def __init__(self,val):
        self.val = val
        self.lchild = None
        self.rchild = None

# 트리
class Tree:
    def __init__(self):
        self.root = None

    # 트리에 노드 추가
    def add(self,val):
        if(self.root == None):
            self.root = Node(val)
        
        else:
            current = self.root
            while(True):
                if(current.val > val):
                    if(current.lchild == None):
                        current.lchild = Node(val)
                        break
                    current = current.lchild

                if(current.val < val):
                    if(current.rchild == None):
                        current.rchild = Node(val)
                        break
                    current = current.rchild
    
    # 후위 순회
    def postOrder(self,node=None):
        global answer
        
        if node == None:
            node = self.root
        
        if node.lchild != None:
            self.postOrder(node.lchild)
        if node.rchild != None:
            self.postOrder(node.rchild)
        answer.append(node.val)


tree = Tree()

# 입력
while True:
    try:
        tree.add(int(input()))
    except:
        break

# 출력
answer = []
tree.postOrder()
print('\n'.join(map(str,answer)))

 

충실하게 작성했지만.. python3에서는 시간 초과가 걸리고, pypy3에서만 통과했다.

 

그래서 트리를 구현하지 않고 해결할 수 있는 방법을 생각해 보았는데, 루트 값을 기준으로 더 작은값과 더 큰값이 구별되는 부분을 찾아서 그 부분을 기점으로 분할 정복을 계속해 나가는 방법이 있었다.

 

대충 이런 식..

 

이런 원리로 코드를 짜 보면 다음과 같다.

 

내 코드:

# dawitblog.tistory.com
import sys
sys.setrecursionlimit(20000)
input = sys.stdin.readline

def postOrder(l,r):
    if l > r:
        return
    
    div = r + 1
    for i in range(l+1,r+1):
        if values[l] < values[i]:
            div = i
            break

    postOrder(l+1,div-1)
    postOrder(div,r)
    ans.append(values[l])

values = []
ans = []
# 입력
while True:
    try:
        values.append(int(input()))
    except:
        break

postOrder(0,len(values)-1)
print('\n'.join(map(str,ans)))