[백준] 5639 이진 검색 트리

🔗 문제 링크

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

💻 코드

import sys
input = sys.stdin.readline 
sys.setrecursionlimit(10**6)
trees = []

while True:
    try:
        trees.append(int(input()))

    except:
        break 


def dfs(arr):

    if not arr:
        return  

    left,right = [],[]
        
    for i in range(1,len(arr)):
        if arr[i] > arr[0]:
            left = arr[1:i]
            right = arr[i:]
            break 

    else:
        left = arr[1:]
        
    dfs(left)
    dfs(right)
    print(arr[0])
   
dfs(trees)

🤷‍♂ 풀이

• 전형적인 트리문제로, 전위순회가 주어지면 어떻게 후위순회로 출력할 것이냐가 관건이다.

• 일단 입력이 끝나면 EOFError가 발생하기에 break로 while문을 종료한다.

• BST에서 첫번째 원소는.. 현재 서브트리의 루트 노드이다.

• arr을 기준으로 left, right를 나눠준다.

  • arr[i] > arr[0] 조건을 통해, 루트보다 큰 곳이 오른쪽 서브트리의 시작 지점이다.

  • arr[0]보다 큰 값이 없다면, 나머지 모든 요소가 왼쪽 서브트리에 해당한다.

• 재귀호출을 통해 왼쪽 서브트리, 오른쪽 서브트리를 탐색하고

• 루트 노드가 가장 마지막에 출력되는 것이 후위순회이기 때문에, 재귀 탐색을 마친 후 print해준다.

• 평균적인 경우 O(nlogn), 최악의 경우 O(n^2)이 된다.

  • 깊이가 log n, 각 깊이에서 O(n) 작업을 수행하는 평균적인 경우

  • BST에서 모든 노드가 한쪽으로 치우치면 최악의 경우

매번 배열을 분할해 비효율적이지 않을까?

• 왼쪽 서브트리와 오른쪽 서브트리를 매번 분할해야한다.

• 인덱스 범위를 사용해 배열 자체를 복사하지않고 서브트리를 지정해보자.

def dfs(arr,start,end):

    if start >= end:
        return

    root = arr[start]
    right_start = end 
        
    for i in range(start+1,end):
        if arr[i] > root:
            right_start = i 
            break 

    dfs(arr,start+1,right_start)
    dfs(arr,right_start,end)

    print(root)

dfs(trees,0,n)

• 배열을 슬라이싱하지 않고, 인덱스 범위만으로 서브트리를 처리한다.

• 각 노드에서 분리 작업에 O(1)만 소요

• 노드 수가 n개라고 하면, 각 노드에서 루트 출력, 인덱스 분리가 이루어지므로 O(n)이다.

• 각 노드에서 배열 복사가 발생하면 재귀호출로 배열 복사가 반복되어 O(n^2)이다.