[Python][백준] 5639. 이진 검색 트리 / 트리,재귀,그래프 탐색 (G4)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

lst = []
while True :
    try: 
        num = int(input())
        lst.append(num)
    except:
        break

def solution(tmp):
    if len(tmp) == 0 :
        return 
    
    tmpL,tmpR = [],[]
    mid = tmp[0]
    for i in range(1,len(tmp)):
        if tmp[i] > mid:
            tmpL = tmp[1:i]
            tmpR = tmp[i:]
            break
    else:
        tmpL = tmp[1:]
    
    solution(tmpL)
    solution(tmpR)
    print(mid)

solution(lst)

 

1. 이 문제에서는 입력값의 개수를 정해주지 않아서 try ~ except 구문으로 입력을 받아야한다.

 

2. 매개변수로 받은 리스트가 빈 값인지 확인하고,  tmpL과 tmpR 빈 리스트를 선언해준다.

 

3. 매개변수로 받은 리스트에 첫 번쨰 인덱스를 mid로 주고, 반복문을 통해 mid보다 큰 값을 찾는다. 

만일 큰 값이 있다면, 해당 인덱스를 기준으로  tmpL과 tmpR으로 나눠주고 break를 한다. 

 

그리고 for문에서 break 되지않고 다 통과한 경우 else 문을 실행한다.

(for ~ else 문이 신기했다... 이런게 있었구나 ?)

 

4.  나눈 tmpL과 tmpR을 재귀 돌려주고, 그 다음 mid를 print 해준다. 

tmpL, tmpR 리스트를 재귀를 통해 타고 타고 넘어가

left 끝의 남아있는 값을 먼저 출력하고, 그 다음 right 끝에 남아있는 값을 출력한다. 

 

[50, 30, 24, 5, 28, 45, 98, 52, 60]

1) 50 [30, 24, 5, 28, 45] / [98, 52, 60] 
2) 30 [24, 5, 28] / [45]  , 98 [52, 60] / [ ]
. . . 

 

위의 순서를 생각하면 좀 더 쉽게 풀이를 생각 할 수 있을 것이다.

 

🐸 내가 작성한 코드 (시간 초과)

import sys
sys.stdin = open("input.txt", "r")
sys.setrecursionlimit(100000) 

class Node():
    def __init__(self,item,left,right):
        self.item = item
        self.left = left
        self.right = right

lst = []
tree = {}

while True :
    try: 
        tmp = int(input())
        lst.append(tmp)
        tree[tmp] = Node(tmp,'.',".")
    except:
        break
    
def tree_left(mid,idx): 
    for i in range(idx,len(lst)):
        if mid > lst[i]: 
            tree[mid].left = lst[i]
            break

def tree_right(mid,tmp_ls):
    # mid 값을 빼고 lst 주기 
    for i in range(len(tmp_ls)):
        if mid < tmp_ls[i]: 
            tree[mid].right = tmp_ls[i]
            mid = tmp_ls[i]
            tree_right(mid,tmp_ls[i+1:])
            break
        else:
            if len(tmp_ls)>1:
                tree_right(tmp_ls[0],tmp_ls[1:i+1])

for i in range(len(lst)):
    tree_left(lst[i],i)
    tree_right(lst[0],lst[1:])

def postoder(node):
    if node.left != ".":
        postoder(tree[node.left])
    if node.right != ".":
        postoder(tree[node.right])
    print(node.item)

postoder(tree[lst[0]])

 

나 같은 경우 이진트리를 완전히 만들고 거기에서 후위순회를 했다.

간단하게 코드를 설명하면, 트리의 left를 먼저 찾아주고

이후 right를 찾아주는 방식으로 했다. 

 

해당 풀이는 시간초과가 뜬 문제이다 ... 

 

📌 문제 코멘트 

주어진 예제를 손으로 구현해보면 재귀가 필요하다는 것은 알 수 있다. 

그리고 리스트를 두개로 분해해야하는 것도 알 수 있다. 

 

조금만 풀어쓰면 그래도 해볼만 한 것 같은데... 

코드 구현 자체는 간단해보이지만 저렇게 생각하는게 너무 어렵다. 

 

(솔직히 다음에 같은 문제가 나와도 풀 수 있을거란 자신이 없다 ㅠㅠ)

---

📚문제

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

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

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

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

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

50
30
24
5
28
45
98
52
60

예제 출력 1 복사

5
28
24
45
30
60
52
98
50

출처