백준 5649: 이진 검색 트리-재귀(Python/파이썬)

메모리초과, 시간초과, 스택오버플로우 다 겪고 나온 코드...

풀이

기본적으로 이진 검색 트리를 전위 순회하면
[노드]+[왼쪽 서브 트리(노드보다 작은 값)]+[오른쪽 서브 트리(노드보다 큰 값)] 으로 구성되게 된다.
그래서 노드 다음 인덱스들을 탐색하되 노드보다 값이 커지는 순간이 오른쪽 서브트리가 시작되는 순간이므로 그 경계 전후로 재귀 함수를 이용해 왼쪽 트리/ 오른쪽 트리를 나눠서 탐색한다.

1. 함수 인자로 인덱스 넘기기

import sys
sys.setrecursionlimit(10**9)

nodes = list(map(int, sys.stdin.read().split()))

def postorder(start, end):
    if start >= end: return
    # mid == end인 경우 처리해줘야

    # 왼쪽 트리 오른쪽 트리 경계 찾기
    mid = end
    for i in range(start+1, end):
        if nodes[start] < nodes[i]:
            mid = i
            break

    # 왼쪽 트리 순회
    postorder(start+1, mid)
   
    # 오른쪽 트리 순회
    postorder(mid, end)
    print(nodes[start])

postorder(0, len(nodes))

2. 함수 인자로 배열 넘기기

import sys
sys.setrecursionlimit(10**9)

nodes = list(map(int, sys.stdin.read().split()))

def postorder(arr):
    if len(arr) == 0:
        return

    # 왼쪽 트리 오른쪽 트리 경계 찾기
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[0] < arr[i]:
            left = arr[1:i]
            right = arr[i:]
            break
     # 왼쪽서브트리만 있는 경우
    if not right:
        left = arr[1:]
        
    # 왼쪽 트리 순회
    postorder(left)
    # 오른쪽 트리 순회
    postorder(right)
    print(arr[0])

postorder(nodes)

for - else

    for i in range(1, len(arr)):
        if arr[0] < arr[i]:
            left = arr[1:i]
            right = arr[i:]
            break
     # 왼쪽서브트리만 있는 경우
    if not right:
        left = arr[1:]

이 부분을 for - else를 써 해결할 수도 있다.

    for i in range(1, len(arr)):
        if arr[0] < arr[i]:
            left = arr[1:i]
            right = arr[i:]
            break
     # 왼쪽서브트리만 있는 경우
    else:
        left = arr[1:]

내가 for-else를 쓰지 않은 이유는 for-else가 for문의 진입 여부만 파악하여 마지막 케이스까지 다 진입했다면 else문이 실행되기 때문이었다.

가장 마지막 반복문(여기서는 i == len(arr)-1)에서 작업이 이루어져도 else문에서 재할당이 이루어져 잘못된 재할당이 발생할 수 있다 생각했기 때문이었다. 이 기회에 for-else구조에 대해 다시 알아본 결과 전에 그러한 방식으로 오류가 났던 코드의 경우 for문 안에 break없이 할당만 이루어져서 오류가 난 것이었다. 위 코드와 같이 for문 안에 break이 있어 루프가 종료될 경우 else는 실행되지 않는다.

for-else 오류 구문

내가 전에 for-else를 사용하여 오류가 났던 코드를 로직만 간단하게 구현하면 다음과 같다.

apple = 0
for i in range(n):
    if i >= 150:
        apple = n
else:
    apple = 169

이런 코드에 n == 151이었다고 하자. 이 경우 의도한 값은 apple = 150이어야 하나 break 없이 루프문이 모두 실행되어 else구문이 실행되고 apple = 169로 재할당되게 된다.
break 중요하다~~~ 루프 종료 조건 잘 걸기~!