트리
시간 제한2초메모리 제한512 MB
괄호로 표현된 이진 트리 모양이 주어질 때, 그 BST 모양을 만드는 1부터 n까지의 순열 중 사전순으로 가장 앞서는 삽입 순서를 출력한다.
문제
이진 탐색 트리(BST)는 모든 노드가 값을 가지며, 임의의 노드에 대해 왼쪽 부분 트리의 모든 값은 그 노드의 값보다 작고 오른쪽 부분 트리의 모든 값은 그 노드의 값보다 큰 이진 트리이다.
서로 다른 정수들의 수열로부터 BST를 만드는 방법은 다음과 같다. 첫 번째 정수가 트리의 루트가 된다. 그다음 두 번째 정수를 본다. 루트 노드의 값보다 작으면 왼쪽 자식이 된다. 그렇지 않으면 오른쪽 자식이 된다. 이후의 원소들은 루트에서 시작하여 트리를 따라 내려가면서, 지나온 노드들과의 비교 결과에 따라 같은 방식으로 왼쪽이나 오른쪽으로 내려간다. 새로운 노드는 진행 방향에 부분 트리가 없는 지점에 도달하면 (잎으로) 부분적으로 만들어진 트리에 삽입된다.
예를 들어 수열 [2, 1, 4, 3]이 만드는 BST는 숫자가 삽입됨에 따라 아래와 같이 만들어진다.
그림 3: BST의 생성
그림 3의 트리 (d)는 다른 두 수열 [2, 4, 3, 1]과 [2, 4, 1, 3]로도 만들 수 있다.
이러한 수열들은 사전식 순서로 비교할 수 있으며, 비교는 왼쪽에서 오른쪽으로 진행하고 같은 위치의 원소들은 숫자 값으로 비교한다. [2, 1, 4, 3], [2, 4, 3, 1], [2, 4, 1, 3]의 비교 결과는 다음과 같으며, 수열 사이의 이 사전식 순서를 “<”로 나타내었다: [2, 1, 4, 3] < [2, 4, 1, 3] < [2, 4, 1, 3].
그림 3의 트리 (d)에 대해 사전식으로 가장 작은 수열은 [2, 1, 4, 3]이다.
트리의 표현을 읽고 그 트리를 만드는 서로 다른 양의 정수 수열 중 사전식으로 가장 작은 수열을 구하는 프로그램을 작성하라. 노드가 n개인 트리에 대해 이 수열은 1부터 n까지의 수를 나열한 순열이다.
문제의 입력에서 트리의 구조는 다음과 같이 (재귀적으로) 나타낸다:
-
노드 하나(잎)는 트리이다:
()
-
TL과 TR이 트리이면 다음도 트리이다:
(TL,)(``,TR)(TL,TR)
입력
입력은 여러 줄로 이루어진다. 각 줄은 길이가 250자 이하이며 위 정의에 따른 트리 하나의 표현을 담는다(사이에 공백은 없다). 노드 하나로 이루어진 트리 ()가 나오면 입력이 끝나며, 이 줄은 처리하지 않는다.
출력
출력은 입력의 각 줄에 대응하는 여러 줄로 이루어진다. 각 줄은 1부터 n까지의 정수를 (n은 트리의 노드 수) 사전식으로 가장 작게 나열한 순열을 공백 하나로 구분하여 담는다.