18240번: 이진 탐색 트리 복원하기

문제 설명

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

18240번: 이진 탐색 트리 복원하기

[문제]

 이진 트리란 각각의 노드가 0, 1, 2개의 자식 노드를 가지는 트리 자료 구조이다.

 이진 탐색 트리란 각 노드의 왼쪽 서브트리(subtree)는 그 노드의 값보다 작은 노드 값들로, 오른쪽 서브트리(subtree)는 그 노드의 값보다 큰 노드 값들로 이루어져 있는 이진 트리를 말한다.

 아래의 그림은 1부터 9까지의 수를 값으로 지닌 노드로 이루어져 있는 이진 탐색 트리의 예시이다.

 또한, 이진 탐색 트리에 새로운 노드를 삽입하는 과정은 다음과 같다.

 루트 노드부터 탐색하여 Insert 하는 값이 현재 노드의 값보다 크면 오른쪽 자식 노드를 방문, 작으면 왼쪽 자식 노드을 방문하는 것을 반복하다가 비어있는 자리에 해당하는 값을 가진 노드를 삽입한다.

 아래는 값이 4인 노드를 루트로 하는 트리에 [2, 3, 5, 1]를 순차적으로 삽입하는 예시이다.

 1부터 N까지의 모든 정수를 한 번씩 포함하고 있는 수열 A1, A2, ..., AN이 있다.

 값이 A1인 노드를 루트로 하는 트리에 A2, A3, ..., AN 을 순서대로 삽입하려 한다.

 N-1개의 노드를 삽입할 때마다 루트에서 그 노드에 도달하기 위해 거쳐야 하는 간선의 수, 즉 노드의 깊이가 주어질 때 A1, A2, ..., AN을 구하는 프로그램을 작성하시오.

 

[입력]

 첫째 줄에 수열의 길이 N이 주어진다. (2 ≤ N ≤ 300,000)

 둘째 줄에는 A2부터 AN을 순서대로 삽입할 때마다 삽입된 노드의 깊이가 공백으로 구분하여 주어진다.

 이때 노드의 깊이는 1이상 N미만의 자연수이다.

 

[출력]

 가능한 수열이 있다면 첫째 줄에 수열 A1, A2, ..., AN의 값을 공백으로 구분하여 출력한다.

 가능한 수열이 여러 개라면 아무거나 출력해도 좋다.

 가능한 수열이 없다면 첫째 줄에 -1을 출력한다.

 

[예제 입력 1]

5
1 2 1 2

[예제 출력 1]

4 2 3 5 1

[예제 입력 2]

9
1 2 2 1 3 2 3 3

[예제 출력 2]

5 3 1 4 9 2 7 8 6

[예제 입력 3]

5
4 3 2 1

[예제 출력 3]

-1

---

풀이

 이 문제는 문제 해석에서 다가오는 모호함 때문에 더 어려웠던 문제였다. 결국 문제에서 요구하는 바는 트리 구조에서 레벨 별 노드의 개수가 주어졌을 때 이를 바탕으로 우리가 판단해서 해당 이진 트리가 가능한 지 불가능한 지, 가능하다면 입력이 어떻게 주어지는 지를 보여주는 것이다. 그러다 보니 어떻게 트리를 구성해야 할 지 감이 잘 오지 않아 헷갈렸는데, 생각을 뒤집어서 문제를 해결했다.

 만약 레벨 별 노드의 개수가 동일하다면, 어떠한 트리 구조든 간에 중위 순회를 하게 되면 노드 번호가 1~노드 개수까지 순차대로 나오게 된다. 결국 트리를 구성하는 것은 내 몫이기 때문에 자신이 구성할 수 있는 가장 간단한 트리 구조를 만들면 되고, 다만 입력을 받는 노드의 깊이(트리 레벨)를 가지고 트리 구조의 타당성이 맞는 지 조사를 하면 된다. 예를 들어 특정 레벨 노드의 개수는 상위 레벨 노드의 개수의 2배 이하가 되어야 하기 때문에, 이를 입력 받을 때마다 확인하여 현재 입력 자체가 말이 되는 지를 구분하면 된다.

 만약 입력 자체가 타당하고, 레벨 별 노드의 개수를 최종적으로 다 받았다면 이를 가지고 중위 순회를 통해 트리 구조를 생성하면 된다. 어차피 주어진 조건은 레벨 별 노드의 개수인 상태에서 중위 순회를 실행하면, 결과는 자연스럽게 레벨 별 노드가 왼쪽에 쏠린 트리 구조가 만들어진다. 그러한 상황에서 레벨 별 트리 구조에 노드 번호를 넣으면 결과가 완성된다.

 이후에는 다시 입력된 노드 깊이를 보며, 단순하게 해당 레벨에 삽입된 노드 번호를 순차적으로 출력하면 된다. 이를 처음에는 레벨 별 큐로 만들어 했으나, 메모리와 시간 소요가 너무 지나치다고 생각되어서 이를 벡터로 변환, 레벨 별 벡터 인덱스를 저장하는 배열을 추가로 만들어 순차적으로 출력하도록 했다.

 

#include <iostream>
#include <vector>

using namespace std;

int levelNodeCount[300001] = { 0, };//레벨별 노드 개수
vector<int> tree[300001]; //트리 자료구조(레벨별 vector)
int levelIndex[300001] = { 0, };//트리 자료구조 레벨별 vector의 인덱스

void inorder(int level, int& nodeNumber) {//중위 순회를 통해 숫자 삽입
	if (levelNodeCount[level] == 0)
		return;

	inorder(level + 1, nodeNumber);

	--levelNodeCount[level];
	tree[level].push_back(nodeNumber++);

	inorder(level + 1, nodeNumber);
}

int main() {
	int N, inputDepth;
	bool isValid = true;
	vector<int> input;//입력 저장용 vector

	cin >> N;

	levelNodeCount[0] = 1;//루트 노드 개수 초기화

	for (int i = 1; i < N; i++) {
		cin >> inputDepth;
		if (levelNodeCount[inputDepth - 1] * 2 < ++levelNodeCount[inputDepth]) //타당성 조사
			isValid = false;

		input.push_back(inputDepth);
	}

	if (isValid) {//앞선 입력이 타당하다면
		int nodeNumber = 1;

		inorder(0, nodeNumber);

		//답안 출력
		cout << tree[0][0] << " ";
		for (int i = 0; i < N - 1; i++)
			cout << tree[input[i]][levelIndex[input[i]]++] << " ";
	}
	else {//타당하지 않으면
		cout << "-1";
	}
	
	return 0;
}

---

결과

 가장 마지막이 큐를 활용한 방법, 이후는 벡터를 사용하여 계속 시간과 메모리를 줄여 나간 방법이다.