파이썬 알고리즘 237번 | [백준 5639번] 이진 검색 트리 - 트리, 재귀

237. 이진 검색 트리

1) 어떤 전략(알고리즘)으로 해결?

• 재귀
• 그래프

2) 코딩 설명

<내 풀이>

import sys
sys.setrecursionlimit(10**5)
lis = []

while True :
    try :
        num = int(sys.stdin.readline().strip())
        lis.append(num)
    except : 
        break

def original(start, end) : # start 는 루트 자리 
    if start > end : 
        return
    standard = end + 1 
    for i in range(start+1, end+1) : 
        if lis[i] > lis[start] :
            standard = i
            break

    original(start+1,standard-1)
    original(standard,end) # end 로 받아줬어야 함 ,, ㅂㄷㅂㄷ 
    print(lis[start])

original(0,len(lis)-1)

< 내 틀렸던 풀이, 문제점>

import sys
lis = []

# (1) 입력이 몇 개 들어오는지 모를 때는 
# while에 try,except 문을 합쳐서 구현
while True :
    try :
        num = int(sys.stdin.readline().rstrip())
        lis.append(num)
    except : 
        break

##########################################################################

def original(root, start, end) : # start 는 루트 자리 
    standard = start+1
    for i in range(start+1, end+1) : 
        if lis[i] > root : 
            print(lis[start+1:end+1], lis[i], root)
            standard = i
            break
        print("std ", standard,"rot", root, 'new', lis[standard])
        original(lis[start+1],start+2,standard-1)
        original(lis[standard],standard+1,len(lis)-1)
        print(root)
    else : 
        return

############################################################################
root = lis[0]
original(root, 0, len(lis)-1)

• 근데 어차피 루트는 해당 문자열에서 start 인덱스에 해당하는 아이지 .
• 루트 불필요하게 넘겨주는 것 제외시키기

import sys
lis = []

# (1) 입력이 몇 개 들어오는지 모를 때는 
# while에 try,except 문을 합쳐서 구현
while True :
    try :
        num = int(sys.stdin.readline().rstrip())
        lis.append(num)
    except : 
        break

##########################################################################

def original(start, end) : # start 는 루트 자리 
    standard = start+1
    for i in range(start+1, end+1) : 
        if lis[i] > lis[start] :
            standard = i
            break
    original(start+1,standard-1)
    original(standard,len(lis)-1)
    print(lis[start])


############################################################################
root = lis[0]
original( 0, len(lis)-1)

• 내가 어려워했던 점 : standard 의 초기값 설정 어케해야하는지
• 멈춤 조건 (return 조건 언제해야하는지)

recursion error

import sys

lis = []
# 입력이 몇 개 들어오는지 모를 때는 
# while에 try,except 문을 합쳐서 구현
while True :
    try :
        num = int(sys.stdin.readline().rstrip())
        lis.append(num)
    except : 
        break

##########################################################################
def original(start, end) : # start 는 루트 자리 
    # end 는 항상 lis 의 마지막 인덱스로 같다 ! 
    # 근데 start 가 end 보다 크게 되면 이제 다 돈 것임
    if start > end : 
        return
    # 우리가 찾는 standard == 지금 트리가 나눠지는 부분을 식별해주는 아이
    # 루트보다 큰 아이가 있으면 걔가 좌우 자식 식별해주는 기준임 
    # 루트/루트보다작은아이(좌)/기준-루트보다큰아이(우)
    #  BUT ! 기준이 없을 수 있음 (좌 아이들에서만 끝나서)
    # 그 경우 고려해서 STANDARD 를 end 보다 큰 수로 해서 다음 재귀에서
    # return 되도록 유도해야 함 ! 
    standard = end + 1 
    # # 루트보다 큰 값이 존재하지 않을 경우를 대비 (출처 블로그)
    for i in range(start+1, end+1) : 
        if lis[i] > lis[start] :
            standard = i
            break
    original(start+1,standard-1)
    original(standard,len(lis)-1)
    print(lis[start])
############################################################################

original(0,len(lis)-1)

출력초과

import sys
sys.setrecursionlimit(10**5)
lis = []
# 입력이 몇 개 들어오는지 모를 때는 
# while에 try,except 문을 합쳐서 구현
while True :
    try :
        num = int(sys.stdin.readline().rstrip())
        lis.append(num)
    except : 
        break

##########################################################################
def original(start, end) : # start 는 루트 자리 
    # end 는 항상 lis 의 마지막 인덱스로 같다 ! 
    # 근데 start 가 end 보다 크게 되면 이제 다 돈 것임
    if start > end : 
        return
    # 우리가 찾는 standard == 지금 트리가 나눠지는 부분을 식별해주는 아이
    # 루트보다 큰 아이가 있으면 걔가 좌우 자식 식별해주는 기준임 
    # 루트/루트보다작은아이(좌)/기준-루트보다큰아이(우)
    #  BUT ! 기준이 없을 수 있음 (좌 아이들에서만 끝나서)
    # 그 경우 고려해서 STANDARD 를 end 보다 큰 수로 해서 다음 재귀에서
    # return 되도록 유도해야 함 ! 
    standard = end + 1 
    # # 루트보다 큰 값이 존재하지 않을 경우를 대비 (출처 블로그)
    for i in range(start+1, end+1) : 
        if lis[i] > lis[start] :
            standard = i
            break
    original(start+1,standard-1)
    original(standard,len(lis)-1)
    print(lis[start])
############################################################################

original(0,len(lis)-1)

<반성 점>

<배운 점>

• 처음 입력을 어케 받아야하나 어려웠는데 파이썬 try-except 문으로 접근해주는 거여따

    try:
        temp = int(input())
    except:
        break

레퍼런스 (참고)

https://imzzan.tistory.com/41