필자의 풀이보다 더 괜찮아보이는 코드를 발견해서 이를 공유하고 설명해보겠다.
해결 방법1
처음은 nodeinfo를 x좌표를 오름차순으로 정렬한다.
그리고 아래의 2가지 규칙을 기반으로 재귀 방식으로 트리를 만들어나가는 방법이다.
- 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
- 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
트리를 만들기 위한 첫 단계는 전체 트리의 루트 노드를 찾는 것으로, 루트 노드는 y 좌표가 최댓값인 노드이다.
nodeinfo는 x좌표를 기준으로 정렬되어 있기 때문에 nodeinfo에서 루트 노드를 기준으로 왼쪽 요소들의 x좌표는 모두 루트 노드의 x좌표보다 작고, 오른쪽 요소들의 x좌표는 모두 루트 노트의 x좌표보다 크다.
이 성질을 이용하여 또 다시 왼쪽, 오른쪽 서브트리에서 각각 루트 노드를 찾고 서브 트리로 쪼개는 과정을 반복하면서 재귀적으로 전체 트리를 형성하는 것이다.
위의 2가지 규칙을 잘 이용한 풀이 방법이라고 할 수 있겠다.
출처 : https://programmers.co.kr/questions/12813
#include <string>
#include <vector>
#include <algorithm>
//00:33
#define vi vector<int>
#define vvi vector<vector<int>>
struct Tree
{
Tree *left;
Tree *right;
int index;
};
using namespace std;
Tree *makeTree(vvi &nodeinfo, int start, int end)
{
if(start > end)
return NULL;
int max = nodeinfo[start][1]; //y좌표의 최대값
int cur = start;//y좌표가 최대인 곳의 인덱스
for(int i = start + 1 ; i <= end ; ++i)
{
if(max < nodeinfo[i][1])
{
cur = i;
max = nodeinfo[i][1];
}
}
Tree *result = new Tree();
result->index = nodeinfo[cur][2];
result->left = makeTree(nodeinfo,start,cur - 1);
result->right = makeTree(nodeinfo,cur + 1,end);
return result;
}
void preorder(Tree *tree, vi &answer)
{
if(tree == NULL)
return;
answer.push_back(tree->index);
preorder(tree->left,answer);
preorder(tree->right,answer);
}
void postorder(Tree *tree, vi &answer)
{
if(tree == NULL)
return;
postorder(tree->left,answer);
postorder(tree->right,answer);
answer.push_back(tree->index);
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
vector<vector<int>> answer;
vvi data;
int size = nodeinfo.size();
for(int i = 0 ; i < size ; ++i)
nodeinfo[i].push_back(i+1);
sort(nodeinfo.begin(),nodeinfo.end());//x좌표 기준으로 오름차순 정렬
Tree *tree = makeTree(nodeinfo,0,size-1);
vi pre,post;
preorder(tree,pre);
postorder(tree,post);
answer.push_back(pre);
answer.push_back(post);
return answer;
}
해결 방법2
필자의 풀이 방법이다.
필자는 구조체 Node로 만든 객체들을 저장한 벡터를 기반으로 트리를 구현했으며, 구조체 Node에는 차례로 노드 번호, x좌표, y좌표, 왼쪽/오른쪽/부모 노드의 벡터상의 인덱스가 저장되어 있다.
그리고 Node 벡터는 트리의 깊이(y)를 기준으로 정렬했고, 깊이가 같다면 x좌표가 작은 순으로 정렬했다. 이렇게 정렬해두면 기준 노드의 부모 노드는 반드시 앞쪽에 있고, 자식 노드들은 존재한다면 반드시 뒷쪽에 있게 된다.
아래의 서브 트리 규칙을 체크하기 위해 함수(check_rule)를 따로 두었으며, 이 함수는 부모 노드부터 루트 노드까지 거슬러 올라가며 규칙을 체크한다.
- 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
- 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
왼쪽 자식 노드를 찾을 때에는 check_rule을 따르면서 기준 노드보다 x, y값이 작은 최초의 노드를 찾으면 되고, 오른쪽 자식 노드를 찾을 때 역시 check_rule을 따르되 기준 노드보다 x값은 크고 y값은 작은 최초의 노드를 찾으면 된다. 노드를 찾았다면 즉시 탐색을 종료해서 시간을 줄이면 된다.
#include <vector>
#include <algorithm>
using namespace std;
struct Node { int num; int x; int y; int left; int right; int parent;};
vector<Node> v;
vector<int> prv;
vector<int> pov;
bool cmp(Node a, Node b) {
if(a.y==b.y) return a.x<b.x;
else return a.y>b.y;
}
void preorder(Node n){ // 전위 순회 과정을 벡터에 저장
prv.push_back(n.num);
if(n.left!=-1) preorder(v[n.left]);
if(n.right!=-1) preorder(v[n.right]);
}
void postorder(Node n){ // 후위 순회 과정을 벡터에 저장
if(n.left!=-1) postorder(v[n.left]);
if(n.right!=-1) postorder(v[n.right]);
pov.push_back(n.num);
}
bool check_rule(int cur, int target){ // 라이언의 트리 노드의 5, 6번째 규칙을 검사
int temp=cur;
while(temp!=-1){
if(v[temp].parent==-1) break;
if(v[temp].x>v[v[temp].parent].x&&v[target].x<v[v[temp].parent].x
||v[temp].x<v[v[temp].parent].x&&v[target].x>v[v[temp].parent].x) return false;
temp=v[temp].parent;
}
return true;
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
vector<vector<int>> answer;
for(int i=0;i<nodeinfo.size();i++) v.push_back({i+1, nodeinfo[i][0], nodeinfo[i][1], -1, -1, -1});
sort(v.begin(), v.end(), cmp); // 트리의 깊이 순으로 정렬
for(int i=0;i<v.size();i++){
for(int pos=i+1;pos<v.size();pos++) { // 왼쪽 노드 찾기
if(!check_rule(i, pos)) continue;
if(v[pos].y<v[i].y&&v[pos].x<v[i].x){
v[i].left=pos;
v[pos].parent=i;
break;
}
}
for(int pos=i+1;pos<v.size();pos++) { // 오른쪽 노드 찾기
if(!check_rule(i, pos)) continue;
if(v[pos].y<v[i].y&&v[pos].x>v[i].x){
v[i].right=pos;
v[pos].parent=i;
break;
}
}
}
preorder(v[0]);
postorder(v[0]);
answer.push_back(prv);
answer.push_back(pov);
return answer;
}
테스트케이스 29개 모두 정답
댓글