백준 #backjoon #5639 #이진검색트리1 5639 이진검색트리 1. 문제분석 트리를 전위순회(preorder)한 결과가 주어질 때, 후위순회(postorder)한 결과를 출력한다. 1 2 3 있으면 전위순회(preorder) : 1 2 3 후위순회(postorder) : 2 3 1 중위순회(inorder) : 2 1 3 (참고) 아이디어 "preorder 입력이 주어지는데, 이 순서대로 이진검색트리(이하 BST)에 삽입하면 BST에 성질에 맞게 입력이 된다. 따라서 이 결과를 preorder로 출력하면 된다." 2. 시간, 메모리 분석 - "노드의 수 10,000개 이하" for each node i // O(N) BST_insert(i) // O(N) 따라서 O(N^2) = 10000 * 10000 = 1억 (1초) OK! - 256MB.... 각 node 1만개.. 2019. 6. 8. 728x90 이전 1 다음
