[백준] DFS, 5639 이진검색트리(파이썬)

백준 18352번 문제를 아슬아슬하게 시간초과가 뜨지 않고 합격했다.

같이 공부를 하는 친구들의 코드를 보던 중 무려 나보다 시간이 3600ms나 빠른 코드를 발견하게 되었다.

처음에는 100ms인 걸 보고 PyPy3로 답을 돌린게 아닌가싶은 의심이 들어 언어를 확인해봤지만 Python3로 작성한 코드였고, 오히려 같은 코드를 PyPy3로 돌려본 결과, 더 시간이 오래걸렸다.

먼저, 나의 코드를 보면 DFS를 선언해주었고, 그 안에서 계속 가지를 뻗어나갈때마다 루트를 처음부터 끝까지 값을 돌려가며 찾아주어야했다.
아래는 나의 코드(3792ms)

import sys
sys.setrecursionlimit(10**9) # 재귀 허용 깊이를 늘려줌(파이썬은 기본적으로 재귀 허용이 낮음)

def dfs(start, end) :

    if start > end :    
        return  # 함수에서 return을 만나면 함수가 종료됨

    mid = end + 1

    # 서브 트리 찾기
    for i in range(start + 1, end + 1) :
        if graph[start] < graph[i] :    # 루트보다 크면 오른쪽 서브 트리
            mid = i
            break

    dfs(start+1, mid-1) # 왼쪽 서브트리 재귀 탐색
    dfs(mid, end)   # 오른쪽 서브트리 재귀탐색

    print(graph[start])

graph = []
# 입력이 언제까지 일지 모르기 때문에 while True: try, except을 활용해야한다.

while True :

    try :
        graph.append(int(sys.stdin.readline().rstrip()))

    except :
        break
# print(graph)
dfs(0, len(graph) - 1)

친구의 코드는 내가 작성한 #서브트리찾기 과정을 binary_search라는 함수를 만들어 시간을 절약했다.

import sys
sys.setrecursionlimit(14000)
input = sys.stdin.readline
print = sys.stdout.write

preorder = []
while True:
    try:
        preorder.append(int(input().rstrip()))
    except:
        break

def solution(root_index, end):
    if root_index > end:
        return 
    if root_index == end:
        print(f'{preorder[root_index]}\n')
        return
    m = binary_search(root_index+1, end, preorder[root_index])
    solution(root_index+1, m-1)
    solution(m, end)
    print(f'{preorder[root_index]}\n')

def binary_search(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if preorder[mid] > key:
            end = mid
        else:
            start = mid + 1

    return end if preorder[end] > key else end + 1

# 인덱스 0부터 len(preorder)-1 까지
solution(0, len(preorder)-1)

코드의 길이를 보기에는 큰 차이가 없어 보이나, 지난 시간에 학습했던 binary search를 활용해 시간을 절약했다. 앞으로 코드를 작성할 때 이미 학습했던 것들을 놓치지 않고 활용하는 과정이 필요한 것 같다.