이진 검색 트리 ( 5639번 )

5639번: 이진 검색 트리

 

나의 풀이

import sys
sys.setrecursionlimit(10 ** 6)

def _make_node():
    answer = []
    while True:
        try:
            answer.append(int(sys.stdin.readline().rstrip()))
        except:
            break
    return answer

def _search(start_idx, end_idx):
    if (start_idx > end_idx):
        return

    right_start_idx = start_idx + 1
    while (right_start_idx <= end_idx):
        if (node[right_start_idx] > node[start_idx]):
            break
        right_start_idx += 1

    _search(start_idx + 1, right_start_idx - 1)
    _search(right_start_idx, end_idx)
    print(node[start_idx])
    
node = _make_node()
_search(0, len(node) - 1)

 

시간 복잡도

재귀 탐색
_search() : n번 탐색 ( 선형 시간 복잡도 )
    while (right_start_idx <= end_idx) : right_start_idx 찾을떄 까지 반복 ( 선형 시간 복잡도 )

해당 파이썬 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )