백준 2263번 파이썬

문제

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

2263번: 트리의 순회

풀이

후위 순위의 마지막 값을 출력하고 그 값을 기준으로 전위 순위를 왼쪽과 오른쪽으로 나누어 각각 재귀 함수를 실행시켰다.

 

처음에는 함수에 슬라이싱을 통해 새로운 리스트를 넘겨주었는데, 메모리 초과가 났다.

첫 번째 실패 코드

def find_pre_order(in_order: list, post_order: list):
    if not in_order:
        return

    print(post_order[-1], end=" ")

    idx = in_order.index(post_order[-1])

    find_pre_order(in_order[:idx], post_order[:idx])
    find_pre_order(in_order[idx + 1:], post_order[idx:-1])


n = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))
find_pre_order(in_order=in_order, post_order=post_order)

메모리 초과를 해결하기 위해서 새로운 리스트를 넘기는 대신 각 리스트의 인덱스만 넘기는 방식으로 변경하였다.

두 번째 실패 코드

import sys
sys.setrecursionlimit(10**9)


def find_pre_order(in_start, in_end, post_start, post_end):
    if in_start > in_end:
        return

    print(post_order[post_end], end=" ")
    idx = in_order.index(post_order[post_end])

    find_pre_order(in_start, idx - 1, post_start, post_start + idx - in_start - 1)
    find_pre_order(idx + 1, in_end, post_end - in_end + idx, post_end - 1)


n = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))
find_pre_order(0, n - 1, 0, n - 1)

이번에는 시간 초과가 났다.

매번 index() 메소드로 인덱스를 찾는 것은 비효율적이라고 생각해서 미리 인덱스를 리스트에 만들어놓고 찾는 방식으로 수정했다.

최종 코드

import sys
sys.setrecursionlimit(10**9)


def find_pre_order(in_start, in_end, post_start, post_end):
    if in_start > in_end:
        return

    print(post_order[post_end], end=" ")
    idx = in_order_idx[post_order[post_end]]

    find_pre_order(in_start, idx - 1, post_start, post_start + idx - in_start - 1)
    find_pre_order(idx + 1, in_end, post_end - in_end + idx, post_end - 1)


n = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))

in_order_idx = [0] * (n+1)
for i in range(n):
    in_order_idx[in_order[i]] = i
    
find_pre_order(0, n - 1, 0, n - 1)