[백준2263&파이썬] 분할정복을 이용해 트리의 preorder 구하기

# 문제

백준 2263 트리의 순회 파이썬 풀이

2263번: 트리의 순회

# 코드

import sys

sys.setrecursionlimit(100_000)

n = int(sys.stdin.readline().strip())
inorders = list(map(int,sys.stdin.readline().split()))
postorders = list(map(int,sys.stdin.readline().split()))



# 1. postorder를 통해서 ROOT노드를 알 수 있다.
  # - 맨 끝 노드가 ROOT 임
# 2. inorder에서 위에서 찾은 ROOT를 찾고 L,R로 쪼갤 수 있다.
  # - inorder에서 오른쪽으로 개수를 센다
  # - 센 개수만큼을 post의 현재 root_index에서 빼준다
  # - 새로운 루트를 발견한다.

result = list()
def inorder(l,r,target) :
  global inorders
  idx = inorders.index(target)
  return (idx-l,r-idx,idx) # 루트에서 왼쪽의 leaf 개수, 오른쪽의 leaf 개수, 현재 위치

call_cnt = 0
def solve(l,r,inorder_l,inorder_r) :
  global postorders,result,call_cnt
  call_cnt+=1
  if l > r :
    return
  target = postorders[r]
  result.append(target)
  left_cnt,right_cnt,inorder_root_idx = inorder(inorder_l,inorder_r,target)
  # print(f"{result} l : {l} , r: {r} , inorder_l : {inorder_l}, inorder_r : {inorder_r}")

  solve(l,l+left_cnt-1, inorder_l,inorder_root_idx-1) # 왼쪽
  solve(l+left_cnt,r-1,inorder_root_idx+1,inorder_r) # 오른쪽

solve(0,n-1,0,n-1)
print(*result)

# 풀이

• 분할정복이 사용된다. 
• inorder와 postorder가 주는 각각의 의미를 이해하니까 풀 수 있었다.
• postorder는 (L , R , root)를 거치게 된다. 즉 현재 내가 보는 범위의 배열의 맨 끝이 ROOT다 이정보를 이용했다.
• inoorder는 (L,root,R)를 거치게 된다. 즉 root가 어디있는지 안다면, 좌,우에 몇개가 있는지 알 수 있다.
• 내 풀이는 post_order를 통해서 root노드를 찾았다. 그리고 inorder에서 찾은 root노드의 인덱스를 알아냈다.
• 그리고 나서 좌,우로 나누어 root기준 왼쪽에 몇개있는지 오른쪽에 몇개가 있는지에 대한 정보를 얻었다.
• 다시 postorder로 돌아와 배열의 범위를 inorder에서 얻어낸 정보로 줄인다. 그리고 그 배열을 이용해서 다시 root를 찾고.. 이 과정을 반복했다.
• 다 풀고나서 리컬젼리미트에 걸려서 이걸 조정해 주어야 했다.
• 다풀고 다른 분들 풀이를 보니까 썩 좋은 풀이는 아닌거 같았다. 
• 특히 inorder에서 인덱스를 찾아줄때 index함수를 이용했는데 여기서 시간을 많이 먹은거 같았다.

def inorder(l,r,target) :
  global inorders
  idx = inorders.index(target)
  return (idx-l,r-idx,idx) # 루트에서 왼쪽의 leaf 개수, 오른쪽의 leaf 개수, 현재 위치

• [].index() 는 O(n)의 시간복잡도가 걸린다. 근데 문제에서 제한시간이 5초라서 괜찮을거 같아서 사용했다.