시간이 많지가 않아 포스팅이 조금씩 늦어지고 있습니다. 이번에는 5번 문제입니다. 정답률이 무려 7% 밖에 되지 않았고, 다 풀고 나서 해설을 읽어보니 트리의 노드를 $O(1)$ 로 찾을 수 있다는 설명이 있어 통과는 하였으나 더 효율적인 방법을 생각해 볼 수 있다는 점을 알았습니다.
이 문제를 풀려면 트리를 규칙에 맞게 생성하여, 실제 preorder, postorder 를 해 보면 풀 수 있음을 알 수 있습니다. 해설에 나온 것처럼, 탐색은어렵지 않습니다. 저는 order 순서를 외울 때, 왼오를 기준으로 중을 맨 앞부터 한칸씩 이동시켜 넣으면 된다 고 외웠습니다. 즉, 중왼오, 왼중오, 왼오중이 됩니다. ㅋㅋ
먼저 직감적으로 알 수 있는 부분은, 트리를 루트부터 구성해야 하기 때문에, 레벨이 가장 높은 트리, 레벨이 같다면 위치가 왼쪽인 노드부터 판별을 해야함을 알 수 있습니다. 따라서 이를 기준으로 정렬을 해줍니다.
규칙에 의하면 이 이진트리의 어떤 노드에 대해, 서브 노드가 왼쪽에 있으면 그 서브노드의 모든 서브 노드들도 노드보다 왼쪽에 있어야 하고, 반대의 경우엔 모두 오른쪽에 있어야 한다는 규칙이 있습니다. 또, 트리의 레벨을 1000으로 제한을 둔 다는 점에서, 트리를 구성할 때 각 노드 별로 따져봐야 할 레벨이 깊어야 1000 이하로 확인할 수 있다는 점을 알 수 있습니다.
따라서 어떤 노드가 부모 노드의 left인지 right인지 체크할 때, 위의 규칙을 참고하여 root 까지 조건을 모두 만족할 경우 연결을 시켜주면 됩니다. 저 같은 경우는, 큐를 만들어 노드 후보군을 하나씩 넣고, 어떤 노드에 대해 큐의 맨 앞에 있는 노드의 left, right 여부를 따져준 후, 판별이 끝난 노드는 큐에서 빼 주는 방식으로 연결하였습니다. 이 때, left 와 right 모두 해당되지 않는 노드의 경우 큐에서 빼주고, 반복자를 1 감소시켜 다음 노드에 대해 다시 검사하도록 하였습니다. 그 다음 preorder, postorder 를 진행하여 정답을 저장하면 됩니다.
최대 레벨 1000에 대해 각 노드별로 탐색하여 연결해주는 작업의 시간복잡도는 레벨 상수가 붙긴 하지만 $O(N)$ 입니다. 정렬에 $O(NlogN)$ 이 소요되므로, 결국 $O(NlogN)$ 에 문제를 풀 수 있음을 알 수 있습니다.
추가로, 소스코드에서 부모가 -1인 경우, 즉 루트에 도달할 경우 무조건 true를 리턴하도록 하였는데, 이렇게 짜도 되는 이유는 문제에서 입력에 모순이 주어지지 않는다고 하였기 때문입니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include <algorithm>
#include <queue>
#include <vector>
typedef long long ll;
using namespace std;
class Node {
public:
int no, level, pos, left, right, parent;
Node() {}
Node(int l, int p) {level = l, pos = p;left = right = parent = -1;}
bool operator < (const Node &n) const { return level == n.level ? pos < n.pos : level > n.level; }
};
vector<Node> vn;
bool isValid(int target, int &source) {
int p = vn[target].parent;
if (p == -1) return true;
if (vn[p].left == target) if (vn[p].pos < vn[source].pos) return false;
if (vn[p].right == target) if (vn[p].pos > vn[source].pos) return false;
return isValid(p, source);
}
void preorder(int idx, vector<int> &ans) {
ans.push_back(vn[idx].no);
if (vn[idx].left > 0) preorder(vn[idx].left, ans);
if (vn[idx].right > 0) preorder(vn[idx].right, ans);
}
void postorder(int idx, vector<int> &ans) {
if (vn[idx].left > 0) postorder(vn[idx].left, ans);
if (vn[idx].right > 0) postorder(vn[idx].right, ans);
ans.push_back(vn[idx].no);
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
vector<vector<int>> answer(2);
int no = 1;
for (auto elem : nodeinfo) vn.push_back({ elem[1],elem[0] }), vn.back().no = no++;
sort(vn.begin(), vn.end());
queue<int> tree;
tree.push(0);
for (int i = 1; i < vn.size(); i++) {
int idx = tree.front();
if (vn[idx].left != -1 && vn[idx].right != -1) tree.pop(), idx = tree.front();
if (vn[idx].left == -1) {
if (vn[idx].pos > vn[i].pos && isValid(idx, i)) {
vn[idx].left = i, vn[i].parent = idx;
tree.push(i);
continue;
} else vn[idx].left = -2;
}
if (vn[idx].right == -1) {
if (vn[idx].pos < vn[i].pos && isValid(idx, i)) {
vn[idx].right = i, vn[i].parent = idx;
tree.push(i);
continue;
} else vn[idx].right = -2;
}
tree.pop(), i--; //Retry node
}
return preorder(0, answer[0]), postorder(0, answer[1]), answer;
}