[Python] 백준 5639번 - 이진 검색 트리 (골드 5)

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 그래프 이론
 - 그래프 탐색
 - 트리
 - 재귀

 

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

5639번: 이진 검색 트리

 

 

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

---

 

처음엔 트리를 구현해서 풀었다.

 

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

class Node:
  def __init__(self, data):
    self.data = data
    self.leftNode = None
    self.rightNode = None
    
  def makeLeft(self, node):
    self.leftNode = node
    
  def makeRight(self, node):
    self.rightNode = node
    
def makeTree(tree, data):
  if tree.data < data:
    if tree.rightNode == None:
      new_node = Node(data)
      tree.makeRight(new_node)
    else:
      makeTree(tree.rightNode, data)
  elif tree.data > data:
    if tree.leftNode == None:
      new_node = Node(data)
      tree.makeLeft(new_node)
    else:
      makeTree(tree.leftNode, data)

root = int(input())
tree = Node(root)

while True:
  try:
    data = int(input())
    makeTree(tree, data)
  except:
    break

# for i in range(8):
#   data = int(input())
#   makeTree(tree, data)
  
def postOrder(tree):
  if tree.leftNode != None:
    postOrder(tree.leftNode)
  if tree.rightNode != None:
    postOrder(tree.rightNode)
  print(tree.data)
  
postOrder(tree)

 

노드를 하나하나 확인한 후 노드를 만들고 만들어주는 과정을 루트부터 찾아서 반복하는 과정을 통했다.

 

그 결과는 시간초과가 발생했다.

 

---

 

그 다음 도저히 모르겠어서 검색을 했다.

 

난 처음엔 배열로 풀려면 완전이진트리여야 한다고 생각햇다.

 

위 문제는 완전 이진트리가 아닌 그냥 이진트리이기 때문에 배열에 빈 공간이 남지 않나? 싶어서 시도조차 하지 않았던 것이다.

 

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

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

 

문제의 예시를 예로들면

 

50 30 24 5 28 45 98 52 60

 

전위순위로 들어온 값을 순서대로 뜯어보면

 

50 30 24 5 28 45 98 52 60

     왼쪽 자식        오른쪽 자식

 

위와 같이 나눠지는걸 확인할 수 있다.

 

그 다음 각 자식들의 구간을 찾은 다음 그 안에서 트리처럼 루트와 자식들을 찾아서 후위순회를 하는 방법이었다.

 

import sys
sys.setrecursionlimit(10**9)

input = sys.stdin.readline

data = []

while True:
    try:
        data.append(int(input()))
    except:
        break
    # 값의 범위가 정해져 있지 않음
    
def post(start, end):
    if start > end:
        return
    mid = end + 1
    
    for i in range(start+1, end+1): # 루트 노드를 제외한 다음순서부터 오른쪽 자식값 찾기.
        if data[i] > data[start]:
            mid = i
            break
        
    # 후위 순회 시작
    post(start+1, mid-1)
    post(mid, end)
    print(data[start])
    
post(0, len(data)-1)

어려운 문제였다.