[백준/Python] 5639번 : 이진 검색 트리

문제

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

이진 검색 트리를 전위 순회한 결과를 보고 후위 순회한 결과를 구하는 문제이다.

풀이

파이썬 EOF 입력 처리?

eof (end of file) : 파일 입출력 시 끝날 때까지 읽어들이는 readline()과 같은 내장 함수를 쓸 때 사용되는 개념

sys.stdin.readline()함수는 eof를 만났을 때 except가 아니라 빈 문자열("")을 반환함

파이썬 내장 함수 input()은 eof를 만났을 때 except를 반환함

입력값에 입력 종결 규칙이 없을 때, 아무 것도 입력하지 않은 경우 빠져나와야 하므로 readline()은 빈 문자열이 들어올 때, input()은 except가 발생했을 때 break 처리를 해주면 됨

while True: # 파이썬 EOF 입력 처리
    try:
        x = int(sys.stdin.readline())
        tree.append(x)
    except:
        break

백준에서는 이렇게 구현하면 정답 처리 해준다고 함

코드1

import sys
sys.setrecursionlimit(10**9)

tree = []

while True: # 파이썬 EOF 입력 처리
    try:
        x = int(sys.stdin.readline())
        tree.append(x)
    except:
        break

def search(arr): # 현재 트리(arr)의 왼쪽 서브 트리, 오른쪽 서브 트리를 찾아 재귀 호출
    if len(arr)==0:
        return
        
    if len(arr)==1: # 서브 트리의 노드가 1개 뿐인 경우 노드값 출력
        print(arr[0])
        return
        
    left, right = 0, 0
    
    for i in range(1, len(arr)): # 왼쪽 서브 트리의 시작 지점 찾기
        if arr[i] < arr[0]:
            left = i
            break
            
    for i in range(1, len(arr)): # 오른쪽 서브 트리의 시작 지점 찾기
        if arr[i] > arr[0]:
            right = i
            break
    
    # 루트->왼->오(전위 순회)에서 왼->오->루트(후위 순회)로 바꾸기 위해 
	# 왼쪽 서브 트리 먼저 재귀 호출 하고 그 다음 오른쪽 서브 트리, 마지막으로 루트를 프린트함
    if left>0 and right>0: # 왼쪽, 오른쪽 서브 트리 모두 존재
        search(arr[left:right]) 
        search(arr[right:len(arr)])
    else: # 둘 중 하나만 존재
        search(arr[1:len(arr)])
        
    print(arr[0])
    
search(tree)

코드2

내 코드에서 왼쪽 서브 트리, 오른쪽 서브 트리의 기준이 되는 mid를 찾는 로직이 너무 비효율적인 것 같아서 

채점 결과 중에 가장 실행 시간이 빠른 코드를 분석해봤다.

 

재귀호출 시 현재 탐색 중인 서브 트리의 시작점, 끝점 (s, e)를 넘겨주어

이 값들을 사용해서 왼쪽, 오른쪽 서브 트리가 모두 있는지 확인했다.

나머지 로직은 같다.

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
l = []
ans = []
while True:
    try:
        x = int(input())
        l.append(x)
    except:
        break
def search(s, e):
    if s>=e: # 노드가 하나 밖에 없는 트리
        ans.append(l[s]) # ans에 추가
        return
    if l[s]>l[e] or l[s]<l[s+1]: # 현재 루트 노드의 오른쪽 자식이 없음 즉 왼쪽 서브 트리만 존재
        search(s+1, e) # 왼쪽 서브 트리만 재귀호출한 후
        ans.append(l[s]) # 루트를 ans에 추가
        return
    for i in range(s+1, e+1): # 왼쪽 서브 트리, 오른쪽 서브 트리 모두 존재하는 경우
        if l[s] < l[i]: # 어디까지가 왼쪽 서브 트리인지 구한 후
            break
    search(s+1, i-1) # 왼쪽 서브 트리 재귀호출
    search(i, e) # 오른쪽 서브 트리 재귀호출
    ans.append(l[s]) # 루트를 ans에 추가

search(0, len(l) - 1)
print('\n'.join(map(str, ans)))