미소를뿌리는감자의 코딩
[백준 2024/09/17] 5639번 이진 검색 트리 본문
1. 문제
https://www.acmicpc.net/problem/5639
2. 접근 방법
pre order 결과를 가지고, post order의 결과를 도출해야 하는 문제였다.
pre order이기에, <루트> <왼쪽 노드> <오른쪽 노드> 순으로 출력될 것이었다.
따라서, 처음 주어진 노드의 키는 전체 binary tree의 root node를 나타낼 것이다.
따라서, 이를 기준으로 다음으로 주어진 노드를 왼쪽에 배치할 것인지, 오른쪽에 배치할 것인지 결정해 주었다.
def get_nodes():
root_num = int(input())
root_node = Node(root_num)
while True:
try:
new_node = Node(int(input()))
cur_node = root_node
while True:
if new_node.root < cur_node.root:
if cur_node.left is None:
cur_node.left = new_node
break
else:
cur_node = cur_node.left
else:
if cur_node.right is None:
cur_node.right = new_node
break
else:
cur_node = cur_node.right
except:
return root_node
위 코드는 입력 처리하는 함수이다.
해당 예제는 몇 개의 노드가 입력으로 주어질 지 언급되어 있지 않기에, try-except 문으로 예외 처리를 해주어야 했다.
except로 예외를 받게 되면, root_node 값을 반환해 주었다.
def postorder(root_node):
stack = []
cur_node = root_node
while root_node:
if cur_node.left:
stack.append(cur_node)
cur_node = cur_node.left
continue
elif cur_node.right:
stack.append(cur_node)
cur_node = cur_node.right
continue
else:
print(cur_node.root)
if stack:
last_visit = stack.pop()
if last_visit.left == cur_node:
last_visit.left = None
else:
last_visit.right = None
cur_node = last_visit
else:
break
다음으로는, post order로 입력 받은 값들을 출력해 주어야 했다.
post order은 왼쪽 노드, 오른쪽 노드를 모두 출력한 후 root node를 출력해 주어야 하기에, 왼쪽 노드, 오른쪽 노드의 유무에 따라 cur_node를 이동시켜 주었다.
처음에는 postorder 함수를 재귀로 작성하여 반환해 주었다. 하지만, recursion error로 인해 통과하지 못하여, stack을 이용해 주었다.
stack으로 pop된 것을 last_visit이라는 변수에 넣어주고, 현재 노드의 위치가 왼쪽, 오른쪽 이냐에 따라 last_visit.left = None or last_visit.right = None 을 처리해 주었다.
하지만, 이보다도 잘 쓴 코드가 있으리라 생각이 들어 다른 코드를 공부해 보게 되었다.
또한, 위 코드는 전위 순회로 주어진 결과를 잘 이용하지 못하였다.
https://ku-hug.tistory.com/132
따랏, 위 블로그를 참고하여 전위 순회를 후위 순회로 효과적으로 전환하는 지에 대해서 생각해 보고, 이를 코드로 작성해 보기도 하였다.
3. 코드
class Node:
def __init__(self, root):
self.root = root
self.left = None
self.right = None
def get_nodes():
root_num = int(input())
root_node = Node(root_num)
while True:
try:
new_node = Node(int(input()))
cur_node = root_node
while True:
if new_node.root < cur_node.root:
if cur_node.left is None:
cur_node.left = new_node
break
else:
cur_node = cur_node.left
else:
if cur_node.right is None:
cur_node.right = new_node
break
else:
cur_node = cur_node.right
except:
return root_node
def postorder(root_node):
stack = []
cur_node = root_node
while root_node:
if cur_node.left:
stack.append(cur_node)
cur_node = cur_node.left
continue
elif cur_node.right:
stack.append(cur_node)
cur_node = cur_node.right
continue
else:
print(cur_node.root)
if stack:
last_visit = stack.pop()
if last_visit.left == cur_node:
last_visit.left = None
else:
last_visit.right = None
cur_node = last_visit
else:
break
if __name__ == "__main__":
root_node = get_nodes()
postorder(root_node)
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
def get_pre():
while True:
try:
pre.append(int(input()))
except:
break
def print_post(start, end):
if start > end:
return
mid = end + 1 # 오른쪽 sub tree 가 없을 때를 대비한, 설정
for i in range(start+1, end+1):
if pre[start] < pre[i]:
mid = i
break
print_post(start+1, mid-1)
print_post(mid, end)
print(pre[start])
if __name__ == "__main__":
pre = []
get_pre()
print_post(0, len(pre) - 1)
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/09/19] 21606번 아침 산책 (0) | 2024.09.19 |
---|---|
[백준 2024/09/18] 1707번 이분 그래프 (0) | 2024.09.18 |
[백준 2024/09/15] 2178번 미로 탐색 (0) | 2024.09.15 |
[백준 2024/09/15] 1991번 트리 순회 (0) | 2024.09.15 |
[백준 2024/09/12] 13334번 철로 (0) | 2024.09.12 |