[BOJ_5639] 이진 검색 트리 (python)

 

5639번: 이진 검색 트리

 

✅ 문제 설명

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

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

 

✅ 접근 방식

처음 접근한 방법

• 전위순회 결과를 이용해서 트리를 만들고, 이를 후위순회하려했습니다.
• 그렇다면 트리를 어떻게 만들 것인가? 이진 검색 트리이므로 루트보다 작은 노드는 왼쪽 서브트리에, 루트보다 큰 노드는 오른쪽 서브 트리에 위치한다는 점을 이용합니다.
• 전위 순회이므로 제일 첫번째 값이 루트값이 되므로 첫번째 값을 기준으로 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 위치시키며 트리를 구성해 나갈 수 있습니다.

이런식으로 루트값(배열의 첫번째값) 기준으로 작은건 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 배치시키면 이진 탐색 트리를 구성할 수 있다.

• 그러나 이 방식으로 풀게 되면 RecursionError가 나왔습니다. sys.setrecursionlimit(10**9)로 recursionlimit을 늘려주어보았는데 recursion Error는 해결되었는데,, 이젠 또 메모리 초과가 뜹니다..

으앙앙

• 따라서 다른 방법을 생각해야했습니다. 😭

이 방법으로 풀었던 코드는 다음과 같습니다.

import sys

def split(list):
    root = list[0]
    left = []
    right = []
    for i in range(1, len(list)):
        if int(list[i]) < int(root):  # 루트보다 작은값은 왼쪽에
            left.append(list[i])
        else:  # 루트보다 큰값은 오른쪽에
            right.append(list[i])

    tree[root] = ['.' if len(left) == 0 else left[0], '.' if len(right) == 0 else right[0]]
    # left, right 의 첫번째 요소가 왼쪽 자식노드, 오른쪽 자식 노드가 된다. 없으면 '.'로 부여함

    if len(left) != 0:
        split(left)
    if len(right) != 0:
        split(right)


def postorder(node):
    if node == '.':
        return
    postorder(tree[node][0])
    postorder(tree[node][1])
    print(node)


numbers = []
lines = sys.stdin.readlines()
for line in lines:
    numbers.append(line.strip())

tree = dict()
split(numbers)

postorder(numbers[0])

 

두번째 시도

• 메모리 초과로 실패했으므로 이번엔 트리를 구성한 다음 후위순회를 하는게 아니라
• 후위순회가 (왼쪽노드)->(오른쪽노드)->(루트) 순으로 방문하고, 전위순회가 (루트)->(왼쪽노드)->(오른쪽노드)순으로 방문한다는 점을 이용해 전위순회의 결과를 이용해 바로 후위순회를 실시하였습니다.
• 즉, 전위순회 결과에서 (루트), (왼쪽서브트리), (오른쪽 서브트리)값을 유추할 수 있기 때문에 이를 이용해 후위순회를 실시한 것입니다.
• (왼쪽서브트리)->(오른쪽 서브트리)->(루트)로 후위순회를 실시해주면 됩니다.

 

으앙앙2

근데 이 코드 역시 실패...

재귀함수로 트리 값이 담긴 list를 넘겨주고, 함수 내에서도 left, right 배열을 이용하고 있기 때문에 재귀가 끝날때까지 이 배열들이 살아있어서 메모리 초과가 발생하게 됩니다.

# 이진 검색 트리
import sys
sys.setrecursionlimit(10**9)

def postorder(list):
    if len(list) == 0:
        return
    root = list[0]
    left = []
    right = []
    for i in range(1, len(list)):
        if int(list[i]) < int(root):  # 루트보다 작은값은 왼쪽에
            left.append(list[i])
        else:  # 루트보다 큰값은 오른쪽에
            right.append(list[i])

    postorder(left)
    postorder(right)
    print(root)


numbers = []
lines = sys.stdin.readlines()
for line in lines:
    numbers.append(line.strip())

postorder(numbers)

 

세번째 시도(실패)

• 후위순회가 (왼쪽노드)->(오른쪽노드)->(루트) 순으로 방문하고, 전위순회가 (루트)->(왼쪽노드)->(오른쪽노드)순으로 방문한다는 점을 이용해 전위순회의 결과를 이용해 바로 후위순회를 실시하는 것은 두번째 시도와 같습니다!
• 리스트의 복사본을 만드는 대신, 시작 인덱스와 끝 인덱스를 전달하여 같은 리스트를 재활용하는 방법을 사용했습니다.

import sys
sys.setrecursionlimit(10**9)

def postorder(start, end):
    if start > end:
        return
    root = numbers[start]
    pivot = end + 1
    for i in range(start + 1, end + 1):  # start+1부터 end까지
        if int(root) < int(numbers[i]):  # 루트보다 큰 값이 나오면 그 값부터 오른쪽 서브트리다.
            pivot = i  # 해당값을 pivot으로 표현
            break

    postorder(start + 1, pivot - 1)
    postorder(pivot, end)
    print(root)


numbers = []
lines = sys.stdin.readlines()
for line in lines:
    numbers.append(line.strip())

postorder(0, len(numbers) - 1)

엥 이건 왜 메모리 초과 뜰까요? 

 

https://www.acmicpc.net/board/view/97559

글 읽기 - 5639 파이썬 어째서 메모리 초과가 나는거죠

 

네번째 시도(성공) 😎

import sys
sys.setrecursionlimit(10**5)

def postorder(start, end):
    if start > end:
        return
    root = numbers[start]
    pivot = end + 1
    for i in range(start + 1, end + 1):  # start+1부터 end까지
        if int(root) < int(numbers[i]):  # 루트보다 큰 값이 나오면 그 값부터 오른쪽 서브트리다.
            pivot = i  # 해당값을 pivot으로 표현
            break

    postorder(start + 1, pivot - 1)
    postorder(pivot, end)
    print(root)


numbers = []
lines = sys.stdin.readlines()
for line in lines:
    numbers.append(line.strip())

postorder(0, len(numbers) - 1)

sys.setrecursionlimit(10**5)로 줄이니 성공했습니다.

 

이 문제의 메모리 제한은 256 MB입니다.

1MB는 1024KB이므로 256MB = 262,144KB이기 때문에.. 정말 아슬아슬하게 통과하였는데.. 더 좋은방법이 있을 것 같습니다.

 

그래서 다른 분들이 제출하신 PyPy3를 사용한 코드 중, 메모리 사용량이 상대적으로 적은 코드를 보았는데,

https://www.acmicpc.net/source/68281690

-> 이렇게 처음 시도처럼 트리를 만들고 후위 탐색을 했음에도 성공한 코드도 있었고,

https://www.acmicpc.net/source/68207122

-> 제 마지막 성공과 같은 로직인데 메모리가 적게 나온 코드도 있었습니다. 저는 (10**4)으로 설정하니까 안돌아가서 10**5으로 설정했는데, 이분은 10**4로 설정해 메모리가 더 적게 나온듯 합니다.

 

✅ 코드 설명

코드 설명은 앞에서 했으므로 이번 포스팅에서는 생략하겠습니다.

 

✅ 최종 코드

import sys
sys.setrecursionlimit(10**5)

def postorder(start, end):
    if start > end:
        return
    root = numbers[start]
    pivot = end + 1
    for i in range(start + 1, end + 1):  # start+1부터 end까지
        if int(root) < int(numbers[i]):  # 루트보다 큰 값이 나오면 그 값부터 오른쪽 서브트리다.
            pivot = i  # 해당값을 pivot으로 표현
            break

    postorder(start + 1, pivot - 1)
    postorder(pivot, end)
    print(root)


numbers = []
lines = sys.stdin.readlines()
for line in lines:
    numbers.append(line.strip())

postorder(0, len(numbers) - 1)

 

❇️ 코멘트

• 파이썬의 삼항연산자에 대해 알게되었습니다.
  파이썬에서는 [조건문] ? [값1] : [값2]이 아니라 [값1] if [조건문] else [값2]로 사용합니다.
• 아직 메모리 초과같은 것에 대한 감이 잡기지 않습니다.. 어떤 계산을 하면 메모리를 많이 잡아먹을지나 이 정도 메모리 제한이면 재귀호출을 많이는 못하겠구나 하는것들에 대한 감..?