5639

날짜 : 2023. 06. 19

사용 언어 : python

 

문제

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

 

 

코드

import sys
sys.setrecursionlimit(10**9)

def search(ro, l, r):
    if len(l) > 0:
        left = list()
        right = list()
        for i in range(1, len(l)):
            if l[i] < l[0]: left.append(l[i])
            else: right.append(l[i])
        search(l[0], left, right)
    if len(r) > 0:
        left = list()
        right = list()
        for i in range(1, len(r)):
            if r[i] < r[0]:
                left.append(r[i])
            else:
                right.append(r[i])
        search(r[0], left, right)
    print(ro) # root 노드 출력
    return


nums = list()
left = list()
right = list()
while True:
    try:
        nums.append(int(sys.stdin.readline()))
    except:
        break

root = nums[0]
for i in range(1, len(nums)):
    if root < nums[i]:
        right.append(nums[i])
    else:
        left.append(nums[i])
search(root, left, right)

 

 

풀이

- 전위로 입력한 경우는 Root - Left - Right

- 전위에서의 Root 는 리스트에서 맨 처음에 오는 노드가 되고, 각각 서브트리는 Root를 기준으로 구성

- 그래서 left, right 리스트를 생성 후 for문을 돌리면서 root와 비교한 후 각각 left, right에 넣은 다음, 후위순회 함수를 호출

(리스트 left, right는 root 노드의 서브트리 리스트)

 

- 후위순회는 Left - Right - Root

- root, left, right로 온 경우 출력하는 것은 무조건 root가 되어야 함

- 그렇기에 서브트리 리스트인 l, r을 순서대로 재귀방식으로 비교 후 전부 탈출한 경우 ro(서브트리의 루트 노드)를 출력

 

알게된 점

- root를 어떻게 뽑아낼까 하다가 전위의 경우에는 리스트의 가장 처음에 오는 원소라는 것을 확인했다.

- 노드의 개수를 맨 처음에 제시하지 않아 다른 사람들의 풀이를 참고했고, 파이썬의 try, except를 알 수 있었다.

- 일반 pypy3로 사용하면 메모리 초과 발생

 

 

참고 사이트

- 파이썬 try-except : https://dojang.io/mod/page/view.php?id=2398 

파이썬 코딩 도장: 38.1 try except로 사용하기