백준 2263번 문제(트리의 순회) 파이썬(Python) 풀이 [로밍맨]

문제 링크

www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

정답 코드는 아래와 같습니다.

import sys
sys.setrecursionlimit(100000)
 
class Node:
  def __init__(self, root, left, right):
    self.value = root
    self.left = left
    self.right = right
 
def findIdx(arr, idx, item):
  while True:
    if arr[idx] == item:
      return idx
    idx += 1
 
def calc(inorder, postorder, iStart, pStart, sz):
  if sz <= 0:
    return None
  root = postorder[pStart + sz - 1]
  rIdx = findIdx(inorder, iStart, root)
  leftSize = rIdx - iStart
  rightSize = sz - leftSize - 1
  left = calc(inorder, postorder, iStart, pStart, leftSize)
  right = calc(inorder, postorder, rIdx + 1, pStart + leftSize, rightSize)
  return Node(root, left, right)
 
def prePrint(tree):
  if tree == None:
    return
  print(tree.value, end = ' ')
  prePrint(tree.left)
  prePrint(tree.right)
 
def solve():
  n = int(input())
  inorder = [int(x) for x in input().split()]
  postorder = [int(x) for x in input().split()]
  tree = calc(inorder, postorder, 0, 0, n)
  prePrint(tree)
  print("")
 
solve()
 

 

Inorder, Postorder, Preorder 이렇게 세 가지에 대해서 이미 이해하고 있다는 전제 하에 설명합니다.

이것에 대한 간단한 설명은 아래 영상 초반부에 있으니 참고 바랍니다.

 

이 문제는 먼저 Inorder 와 Postorder 가 주어졌을 때, Preorder 가 결정되는지 확인하고,

(결정되기 때문에 문제로 주어졌을 것이지만) "어떻게" 결정되는지를 알아내야 합니다.

다시 말해서 어떤 특성 또는 규칙이 있는지를 알아내야 합니다.

 

(제가) 찾아낸 특성에 대한 내용을 설명 드리는 것은 어렵지 않습니다.

다만 꼭 말씀드리고 싶은 것은 그 특성을 어떻게 스스로 생각해낼 수 있는가 입니다.

사람마다 그 방식은 다를 수 있지만 저의 방식은 직접 해보는 것입니다.

실제 몇 가지 상황을 그려보고 어떤 특성을 찾아내는 것입니다.

 

728x90

 

결국 다음과 같은 특성이 있다는 것을 알아냅니다.

Postorder의 맨 마지막에 있는 root값을 먼저 알아내면,

Inorder에서 어디부터 어디까지가 left 이고, 어디부터 어디까지가 right 인지 알아낼 수 있습니다.

그럼 이 정보를 바탕으로 Postorder 에서 left가 어디까지인지, right가 어디인지 알아낼 수 있습니다.

결국 tree를 구성해나갈 수 있게 됩니다.

정답은 구성한 tree를 Preorder 로 출력해주기만 하면 됩니다.

 

Python은 다른 언어에 비하여 함수를 호출 할 수 있는 depth의 제한이 큽니다.

따라서 가능하면 저는 재귀 방식을 이용하지 않는데,

이 문제는 재귀를 사용하지 않으러면 너무 복잡해져서 부득이 재귀 방식을 사용하였습니다.

그리고 depth 가 깊기 때문에 위 코드의 첫 번째, 두번째 줄과 같이 recursion 제한을 풀어주었습니다.

 

풀이는 아래 영상 참고 바랍니다.

www.youtube.com/watch?v=18ncLrRKGiM

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)