문제
이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
입력
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.
출력
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
풀이
처음에 든 생각은 이진검색트리의 add 기능에 post_order 기능을 넣으면 되지 않을까였다.
하지만 결과는 시간초과....
전위로 들어오는 입력을 재귀로 이용하면 된다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
def recur(left, right):
if left == right:
print(a[left])
return
parent = a[left]
for i in range(left + 1, right + 1):
# 현재 parent보다 높은 값이 나오면 해당 인덱스 i부터는 우측영역에 들어감
if parent < a[i]:
recur(left + 1, i - 1) # 좌측
recur(i, right) # 우측
print(parent) # 루트
return
# 우측영역이 존재 하지않는다면 parent인 a[left] 는 제외하고 뒷 영역만 실행
if left + 1 <= right:
recur(left + 1, right) # 좌측
print(a[left]) # 루트
a = []
while True:
try:
a.append(int(sys.stdin.readline()))
except:
break
recur(0, len(a) - 1)전위로 들어오는 입력은 영역을 2가지로 나누어 볼 수 있다.
첫 인덱스보다 작은영역, 큰영역이다. 여기서 작은영역으로 들어가면 또 이 영역도 첫 인덱스보다 작은영역, 큰영역이 나뉘게된다.
그렇다 재귀를 쓰면된다.
간단하게 아래의 3가지를 이용하면 된다.
- func(작은영역)
- func(큰영역)
- print(첫 인덱스 값)
하지만 위의 코드를 제출 했을 때 걸린 시간은 1700ms 였고, 같은 맥락의 다른 코드를 봤을 때 40ms인걸 보고 내 코드가 불필요한 검사를 하고 있는건 아닌지 수정에 들어갔다.
우선 위의 코드에서 첫 인덱스 값과 두번째 인덱스부터의 값들과 비교하면서 큰 값이 나오면 2가지 영역을 찾는데 성공한 것이고 재귀를 들어가게 된다.
여기서 꼭 2가지 영역이 있다는 보장이 없다.
따라서 작은영역만 있을경우, 큰영역만 있을경우를 미리 판단하면 빨라지지 않을까라는 생각으로 첫번째 원소의 값 즉, 루트의 값과 바로 다음 원소의 값 또는 맨 뒤의 값과 비교를 하여 불필요한 검사를 줄였다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
def recur(left, right):
# left는 시작 인덱스
# right는 끝 인덱스
if left == right:
print(a[left])
return
parent = a[left]
# 좌측, 우측 영역 구분이 없을 때
# 따로 처리 해줘서 불필요 연산 줄임
if a[left] > a[right] or a[left] < a[left + 1]:
recur(left + 1, right)
print(parent)
return
# 좌측, 우측 영역 나뉠 때
for i in range(left + 2, right + 1):
# 현재 parent보다 높은 값이 나오면 해당 인덱스 i부터는 우측영역에 들어감
if parent < a[i]:
recur(left + 1, i - 1) # 좌측
recur(i, right) # 우측
print(parent) # 루트
return
a = []
while True:
try:
a.append(int(sys.stdin.readline()))
except:
break
recur(0, len(a) - 1)
