[백준 2263번] 트리의 순회

mokomoko·2022년 1월 20일
1

1. 문제


n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

제한 사항

시간 : 5 초
메모리 : 128 MB

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

- 키워드

  • 중위 순회와 후위 순회의 특징을 통해 노드를 추출하자.
  • 시간과 메모리의 양을 잘 참고하도록 하자.

2. 풀이


이 문제를 읽었을 때, 지난 번 문제를 잘 생각해봤다.

중위 순회를 보면 부모 노드를 기준으로 왼쪽 오른쪽으로 나눠 지는 것을 볼 수 있고,

후위 순회를 보면 부모 노드는 항상 가장 끝에 있다는 것을 알 수 있다.

이 특징을 통해서 preorder를 구할 수 있다.

다음 테스트케이스를 살펴보자

11
8 4 2 9 5 1 10 6 3 11 7
8 4 9 5 2 10 6 11 7 3 1

후위 순회의 맨 끝에서 부모 노드를 찾고, 중위 순회를 기준으로 나눈다.

전위 순회는 왼쪽 노드의 부모노드부터 탐색하므로 왼쪽 노드의 부모노드를 먼저 찾는다.

이쯤 되면, 무슨 알고리즘을 묻는 것인지 알 것이다.

바로, 분할 정복을 이용해 푸는 것이다.

해당 과정을 계속 진행해보자.

다음 왼쪽 노드에서는 부모 노드가 4고,

자식 노드는 8밖에 남지 않으므로 8이 그 다음으로 들어온다.

오른쪽 노드인 9,5 역시 같은 과정을 거친다.

아까와 같은 경우로 나왔고, 같은 과정을 거치므로

6, 10, 7, 11 순서로 들어온다.

결과로 preorder는 다음과 같이 나온다.

3. 소스코드


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100001)

preorder = []
inorder = []
postorder = []

# def divide(inorder,postorder): 메모리 초과
# 	if len(inorder) == 1:
# 		preorder.append(inorder[0])
# 	elif inorder and postorder:
# 		for i in range(len(inorder)):
# 			if inorder[i] == postorder[-1]:
# 				preorder.append(postorder[-1])
# 				divide(inorder[:i],postorder[:i])
# 				divide(inorder[i+1:],postorder[i:-1])

def divide(il,ir,pl,pr):
	if ir - il != pr - pl:
		return
	if il < ir and pl < pr:
		for i in range(ir-il):
			if inorder[il+i] == postorder[pr-1]:
				preorder.append(postorder[pr-1])
				divide(il,il+i,pl,pl+i)
				divide(il+i+1,ir,pl+i,pr-1)


def solution():
	divide(0,N,0,N)
	for i in preorder:
		print(i,end=" ")

if __name__ == "__main__":
	N = int(input())
	inorder = list(map(int,input().split()))
	postorder = list(map(int,input().split()))
	solution()

주석 처리 된 부분은 슬라이싱을 통해 구현한 것이다.

로직으로는 같은 성능이지만, 위의 경우 메모리 초과가 나온다.

n이 100,000까지 나오므로, 메모리에 과부하가 올 수도 있으므로,

전역변수로 선언해서 인덱스값만 활용하도록 했다.

depth 이슈가 있으므로 sys.recursionlimit(100001)을 추가하도록하자.

4. 후기


평소에 하는 방식으로 하려다가 메모리초과가 나온 것을 보고

인덱스 값을 넘겨주는것으로 수정하려다보니 머리가 상당히 아팠던 거 같다..

문제를 푸는 당일 머리에 과부하가 와서 다음 날 해결하기로 했다.

역시 알고리즘은 충분한 휴식이 필요한 거 같다..

다음 날 몇 분채 걸리지않아 바로 풀 수 있었다.

메모리 제한을 대비해 인덱스화 하는 것도 연습할 필요가 있어보인다.

0개의 댓글