[백준 5639번] 이진 검색 트리 (python)

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

 

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

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

 

기록

(트리 2일차) 시간초과 때문에 고생했다...... 

어제부터 알고리즘 매일 풀려고 시작했는데 기록 남기면 좋을 것 같아서 글 작성해보려고 한다. 나중에는 댓글도 달리고 했으면 좋겠다:) 

 

구현

import sys
sys.setrecursionlimit(10 ** 9)

# 변수 초기화
note = []
count = 0
while count <= 10000:
    try:
        temp = int(input())
    except:
        break
    note.append(temp)
    count += 1

def divide(note, start, end):
    # base case
    if end==start:
        return []
    if end-start<=1 :
        return [note[start]]

    # step
    root = note[start]
    find_idx = end
    for i in range(start+1, end):
        if note[i] > root :
            find_idx=i
            break
    tree = divide(note, start+1, find_idx) + divide(note, find_idx, end) + [note[start]] # 왼+오+루트
    return tree

tree = divide(note, 0, len(note))
for t in tree:
    print(t)

1. setrecursionlimit

재귀함수의 깊이가 기본 1000으로 세팅되어 있기 때문에 제한을 늘려주도록 설정한다.

 

2. 입력

이 문제는 입력부분부터 그동안 풀던 문제와 달라서 당황.. 구글링해보고 try except문으로 사용해서 입력이 잘못됐을 때 break하도록 구현했다.

 

3. divide 함수

divide 함수는 전위 순회(루트-왼쪽-오른쪽)에서 왼쪽, 오른쪽, 루트를 분리하여 후위 순회(왼쪽-오른쪽-루트) 순서로 재조립하는 과정을 반복하도록 구현된 재귀함수이다.

이 부분에서 시간초과때문에 고생해서 고친과정 기록해놔야겠다. 아래와 같이 3가지 버전이다!

 

<ver 1> 

def divide(note):
    # base case
    if len(note)<=1 : return note

    # step
    right = []
    left = []
    root = note[0]
    for n in note:
        if n < root: left.append(n)
        elif n > root : right.append(n)
    tree = divide(left) + divide(right) + [note[0]]
    return tree

for문 안에 보면 루트를 기준으로 작은 숫자들을 left 배열, 큰 숫자들을 right 배열에 추가하는 과정이다.

문제 : for문이 break없이 끝까지 다 돈다.

해결 : 작은숫자들 먼저나오고 그 다음 큰 숫자들이 순서대로 나오니까 구분하는 인덱스를 찾으면 멈추도록 변경

 

<ver 2>

def divide(note):
    # base case
    if len(note)<=1 :
        return note

    # step
    root = note[0]
    find_idx = 0
    for i in range(len(note)):
        if note[i] > root : break
        find_idx=i+1
    tree = divide(note[1:find_idx]) + divide(note[find_idx:]) + [note[0]] # 왼+오+루트
    return tree

위의 문제 해결했는데도 시간초과 에러 떠서 구글링해봤다.

문제 : 슬라이싱에서 시간이 꽤 많이 드는것 같다. 찾아보니 a:b로 슬라이싱 했을 때 O(b-a)라던데 슬라이싱된 배열이 길수록 시간이 많이 들 것 같긴하다.

해결 : 슬라이싱 없애고 배열과 인덱스 각각을 넘겨주도록 변경

 

<ver 3>

def divide(note, start, end):
    # base case
    if end==start:
        return []
    if end-start<=1 :
        return [note[start]]

    # step
    root = note[start]
    find_idx = end
    for i in range(start+1, end):
        if note[i] > root :
            find_idx=i
            break
    tree = divide(note, start+1, find_idx) + divide(note, find_idx, end) + [note[start]] # 왼+오+루트
    return tree

해결!!