백준 5639 이진 검색 트리 파이썬 풀이

난이도 : 골드5

풀이일 : 2403041

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

5639번: 이진 검색 트리

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

 

---

풀이 코드

import sys
# 재귀호출 깊이 제한 설정
sys.setrecursionlimit(10 ** 9)


# 후위 순회 재귀 함수
def sol(root, end):
    # 더 이상 탐색할 노드가 없을 때
    if root > end:
        return

    # 현재 노드 값 저장
    temp = nums[root]
    # 루트 노드보다 큰 값이 나오는 인덱스
    big = end + 1

    # 루트 노드보다 큰 값 찾기
    for i in range(root + 1, end + 1):
        if temp < nums[i]:
            big = i
            break

    # 왼쪽 서브트리 재귀 함수 싫행
    sol(root + 1, big - 1)
    # 오른쪽 서브트리 재귀 함수 실행
    sol(big, end)
    # 현재 노트 출력
    print(nums[root])


# 입력 처리
nums = []
while True:
    try:
        num = int(sys.stdin.readline())
    except:
        break
    nums.append(num)

sol(0, len(nums) - 1)

배운 것

• sys.setrecursionlimit(10 ** 9) : 10의 9 제곱까지로 재귀 가능 횟수 설정

코드 구성

• 이진검색트리의 전위 순회의 결과, 왼쪽 서브트리에는 루트보다 작은 수들이, 오른쪽 서브트리에는 루트보다 큰 수들이 오는 점을 이용
• big : 루트 노드보다 큰 수가 나오는 인덱스를 저장
  • 초기 값은 루트 노드보다 큰 값이 없을 경우를 대비해 +1 로 설정
• 왼쪽 서브트리, 오른쪽 서브트리에 대해 재귀 호출
• 호출 후 되돌아오면 현재 노드 출력

---

느낀점

• 어제 엄청 오래 풀었는데 틀린 방법이어서 실패하고 오늘은 다른 사람의 코드를 참고해 풀었다. 이렇게 풀어야 알고리즘이 는다는데 이제 좀 늘게 될까
• 트리는 너무 재밌는데 어려우니까 한 동안 트리 문제들을 조금 파봐야지