[BOJ][Python3/PyPy3] 5639 - 이진 검색 트리

이전의 등산 문제와 마찬가지로..

수많은 "맞왜틀?!!" 을 외치게 만든 문제.

1시간 넘도록 고생한 흔적... 30분전의 첫 AC는 정답인 분의 코드를 복붙해서 받은 AC이다.

분명 알고리즘은 맞는 것 같은데, 다른 사람의 정답 알고리즘과 같은 틀의 알고리즘인데

왜 런타임에러가 나고, 시간초과가 발생하는 것인지 몰라서 고생했던 문제이다.

 

다른 사람의 코드와 내 코드를 비교하면서 배운 점들을 기록해보고자 한다.

다음은 내가 비교했던 분의 정답코드가 담긴 블로그 주소이다.

https://developmentdiary.tistory.com/442

[Python]트리 백준 5639

================================================

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

5639번: 이진 검색 트리

문제는 이진검색트리의 전위순회가 주어진 경우, 후위순회를 출력하는 것이다.

지난 여름방학 때, 알고리즘 캠프에서 트리를 학습하며

이진트리의 전위순회/ 중위순회/ 후위 순회 중 2가지를 이용해

나머지 순회를 알아내는 문제를 푼 적이 있었다.

 

사실 그 문제를 풀면서 전위순회에서 후위순회를 찾는 기본적인 방법은 쉽게 떠올릴 수 있었다.

어떤 트리의 전위 순회에서 맨 첫번째 방문 노드는 루트노드 라는 것.

 

이진트리에서는 나머지 노드 리스트를 특정 기준으로 자르면 됐었다.

그리고 자른 각각의 리스트에 대해 첫번째 노드가 해당 리스트로 구성된 서브트리의 루트노드다.

 

이 아이디어를 이 문제에서는 상황에 맞게 조금 변형시키면 되었었다.

이 문제는 자르는 기준이 루트노드 아래에 딸린 노드들 중 루트노드보다 큰지 작은지를 기준으로 자른다.

 

1. 런타임에러

''' 이진 검색 트리 '''
import sys
from collections import deque
def f(start, end):
    #print(start,end)
    if start == end:
        print(pre[start])
    else:
        root = pre[start]
        l_s, l_e, r_s, r_e = 0, 0, 0, 0
        for pos in range(start+1, end+1):
            if pre[pos] < root and not l_s:
                l_s = pos
            elif pre[pos] > root and not r_s:
                if l_s:
                    l_e = pos-1
                r_s = pos
        if r_s:
            r_e = end
        else:
            l_e = end
        if l_s:
            f(l_s, l_e)
        if r_s:
            f(r_s, r_e)
        print(root)

pre = deque()

while True:
    try:
        pre.append(int(sys.stdin.readline()))
    except EOFError:
        break
'''while True:
    check = sys.stdin.readline().rstrip()
    if check == '#':
        break
    pre.append(int(check))'''

f(0, len(pre)-1)

내가 맨 처음 제출했던 코드이다.

막연하게 전위순회 순서를 덱에 넣고 왼쪽에서 팝하면 그게 루트노드니까

그걸로 어찌어찌 하면 되지 않을까 라는 생각으로 덱을 썼었다.

 

사실 백준에서 입력의 종료 기준을 입력받지 않는 문제를 자주 풀어보지 않았고

막연하게 EOF 처리만 하면 된다는 정보만을 가지고 EOF 에러로 예외처리를 하였다.

 

당연히 되겠지 싶어서 제출한 결과는 런타임에러.

로컬에서 테스트할때는 주석처리한 #을 입력의 종료로해서 테스트했기 때문에

당연히 될 줄 알았다고 생각한게 오산이었다.

 

런타임 에러의 예상 이유 1 : EOF 에러가 아닌 Value 에러

파이참에서 Ctrl + D 를 이용해 강제로 EOF를 발생시키니 오류가 발생했는데

발생한 오류는 EOF 오류가 아니라 Value 에러였다.

'' 를 int로 변형할 수 없다는 오류였다..

 

이 오류의 해결은 그냥 특정 예외를 지정하지 않고 except 문만 써서 해결했다.

 

런타임 에러의 예상 이유 2 : 입력이 없을 경우에 발생하는 Index 에러

 

f(0,len(pre)-1)

 

이 코드가 문제 원인이 아니었나 싶다.

문제에서 "노드의 수는 10,000개 이하이다." 라고 하였다.

즉 아무런 입력없이 바로 EOF 가 발생할 수도 있다는 것.

그 상태로 이 함수를 실행시키면 인덱스 에러가 발생했다.

 

이 오류의 해결은

if pre:

라는 코드를 넣어서 리스트에 값이 있을 때 함수가 실행되도록 했다.

 

런타임 에러의 예상 이유 3 : 재귀 깊이

 

재귀함수를 사용해 탐색할 경우 파이썬은 재귀 깊이의 제한을 기본적으로 낮게 잡아두기에

재귀 깊이가 깊어질 경우 에러를 발생시키는 점을 간과했었다.

 

sys.setrecursionlimit(10**9)

이 코드를 이용해 해결하였다.

 

2. 시간초과

 

나에게 깊은 스트레스를 안겨준 '시간초과' 이다.

분명 알고리즘에 문제는 없다고 생각했다.

정답 코드를 참고했던 블로그에도 적혀 있듯이,

그 분이 AC를 받은 코드의 알고리즘과 내 알고리즘은 기본적으로 똑같은 알고리즘이었다.

 

등산문제를 풀 때처럼 정답인 코드와 내 코드의 구조를 맞추고, 차이점을 찾아보았다.

 

1. 예외 처리 방법이 다르다.

내가 이 부분을 고려한 이유는 질문 글을 검색하다가

예외처리가 제대로 안되어 더이상 입력으로 주어질 것이 없음에도, 무한히 계속 입력받기를 기다려서

시간초과가 발생하는 케이스가 있었음을 알게 되었기 때문이다.

count = 0
while count <= 10000:
    try:
        num = int(input())
    except:break
    post.append(num)
    count += 1

AC를 받은 코드에는 예외처리가 다음처럼 되어있었다.

이 예외처리를 내가 예외처리 한 방식으로 바꿔서 제출해보았다.

 

결과는 AC였다.

따라서 예외처리는 시간초과에 영향을 주는 요인이 아니었다.

 

2. 알고리즘의 구현방법이 다르다.

 

기본적으로

 

start, end 지점을 받은다음

start 지점의 노드값을 루트노드(기준값)으로한다.

start+1 부터 end 번째의 노드들을 루트노드와 비교해서

루트노드보다 작으면 왼쪽 서브트리에 있는 것으로,

루트노드보다 크면 오른쪽 서브트리에 있는 것으로 간주한다.

각 서브트리에 대해 위 과정을 반복한다.

 

라는  알고리즘틀은 같았다.

 

나의 알고리즘 구현 방법은 다음과 같았다.

def f(start, end):
    #print(start,end)
    if start == end:
        print(pre[start])
    else:
        root = pre[start]
        l_s, l_e, r_s, r_e = 0, 0, 0, 0
        for pos in range(start+1, end+1):
            if pre[pos] < root and not l_s:
                l_s = pos
            elif pre[pos] > root and not r_s:
                if l_s:
                    l_e = pos-1
                r_s = pos
        if r_s:
            r_e = end
        else:
            l_e = end
        if l_s:
            f(l_s, l_e)
        if r_s:
            f(r_s, r_e)
        print(root)

왼쪽 서브트리, 또는 오른쪽 서브트리가 없을 수도 있다는 특이케이스를 고려해서

왼쪽 서브트리의 스타팅과 엔딩포인트

오른쪽 서브트리의 스타팅과 엔딩포인트를 따로 관리하였다.

스타트와 엔딩포인트를 모두 순회화며

왼쪽 서브트리의 엔딩포인트를 갱신하고, 오른쪽 서브트리의 스타팅과 엔딩포인트를 갱신한다.

 

만약 왼쪽 스타팅이 갱신이 안되어있다면, 왼쪽 서브트리에는 아무것도 없는 것이고

오른쪽 스타팅이 갱신이 안되어있다면, 오른쪽 서브트리에는 아무것도 없는 것이다.

그리고 각각의 서브트리에 대해 노드가 존재할 경우 해당 서브트리에 대해 재귀적으로 함수를 호출한다.

 

말로만 적어도 매우 복잡하다...

그러나 알고리즘 자체가 틀리지는 않았다고 생각한다.

 

(지금와서 생각해보니 이 문제는 트리라는 자료구조에 대해 이분탐색을 진행하는 것과 비슷한 느낌인데,

내가 짠 코드를 이분탐색의 경우로 적용해 바라보면 "이분" 시킬 커팅지점만 찾으면 될 것을

왼쪽 영역, 오른쪽 영역 각각의 경계값을 굳이 찾아내는 느낌이다.)

 

정답코드의 알고리즘 구현 방법은 다음과 같았다.

    if start > end:
        return

    division = end+1#나눌위치
    for i in range(start+1,end+1):
        if pre[start] < pre[i]:
            division = i
            break

    f(start+1, division-1)#분할 왼쪽
    f(division, end)#분할 오른쪽
    print(pre[start])

내가 구현한 것보다는 매우 짧고 간단했다.

이분탐색에서 느꼈던 걸 또 느끼는 데자뷰

 

어차피 이미 루트노드를 기준으로 왼쪽값들은 모두 루트노드보다 작은 값,

오른쪽 값들은 모두 루트노드보다 큰 값 임이 보장되어 있다.

따라서 루트노드보다 작은값이 나오는 마지막 인덱스와 루트노드보다 큰 값이 나오는 첫인덱스

이 경계 인덱스를 찾기만 하면 나머지는 구할 필요가 없다.

 

그 경계값을 찾자마자 break하여 빠져나오고

왼쪽 오른쪽으로 함수를 실행시킨다.

 

이 경우에는 start == end 일때 출력하는 것이 아니라.

기본적으로 출력은 모두 하되

start > end 으로 역전되었을 때, 출력하기 전에 미리 함수를 끝내는 것이다.

 

이렇게 하면 나는 start부터 end까지 모든 노드를 순회하고

단순히 순회만 하는게 아니라

매 순회과정마다 값을 갱신하고 처리하는 과정을 거쳐야 했다.

 

그러나 이 AC 코드는 값의 처리 및 갱신은 루트노드보다 처음으로 큰 값이 나오는 인덱스가 나올 경우에만 하고

그 이후에는 break를 하여 쓸데없이 모든 노드를 순회하지 않아 처리과정을 대폭 줄인 효율적인 코드였다.

 

무엇보다 간결하고 직관적인 코드다.

 

그래서 최종적으로 다음과 같이 제출하여 AC를 받았다.

''' 이진 검색 트리 '''
import sys
sys.setrecursionlimit(10**9)
def f(start, end):
    if start > end:
        return
    else:
        root = pre[start]
        div = end + 1
        for pos in range(start+1, end+1):
            if root < pre[pos]:
                div = pos
                break
        f(start+1, div-1)
        f(div, end)
        print(root)

pre = []
while True:
    try:
        pre.append(int(sys.stdin.readline()))
    except:
        break
if pre:
    f(0, len(pre)-1)

런타임에러, 시간초과 문제를 해결하고나니 첫 코드에 비해 매우 깔끔해졌다.

(사실 if pre: 코드 줄은 필요 없는 줄이다. if start > end: return 코드를 통해 예외가 처리되기 때문이다.)

 

오늘의 배운점 요약

1. EOF 처리는 EOFError 가 아니라 그냥 Except 로 하자.

2. 알고리즘의 큰 틀 아이디어는 맞았는데 시간초과가 난다면,

알고리즘 세부적인 구현과정에서 비효율적인 부분이 있을 수 있다.

(나는 이분탐색이 관련된 경우 비효율적으로 구현하는 경향이 있는 것 같다.)

3. 맞왜틀은 없다. 틀왜틀만 있을 뿐