이번 문제는 이진트리를 사용하는 문제이다.
여기서 내가 헤매었던 부분이기도 하고, 핵심이기도 한 부분이 바로,
- 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
- 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
이부분이다.
왜그럴까? 그냥 한번 살펴보자
이진트리를 안다면 일단 루트노드를 7로 잡고,
그다음 바로 한칸 아래인 5에 해당하는 노드인 4,2 중에서
7보다 작은쪽인 4가 왼쪽, 7보다 큰 2가 오른쪽으로 배치하는것까지는
쉬울것이다.
그렇다면 그다음 6이 들어올때는 당연히 가장 작으니까 4번 노드의 왼쪽에 위치할것이다.
그런데 그다음 들어올 1이 문제다.
왜일까?
6보다는 크니까 6보다 오른쪽에 있는건 알겠는데,
4와 2번 노드로만 왼쪽, 오른쪽을 판단하면 불가능하다.
왜냐하면 4번노드의 x값은 3이고 2번노드의 x값은 11이므로
다음차례에 올 1번노드는 x값이 5이니까 4번노드의 오른쪽과, 2번노드의 왼쪽 전부 해당이 된다.
그러면 1번노드는 어디에 넣어야할까? 바로 4번노드의 오른쪽이다.
그 이유는 4,2번에 해당하는 세로축 5 위에 루트노드인 7이 있기 때문이다.
만약 1번노드가 2번노드의 왼쪽으로 들어가게 되버리면, 7번노드의 x값은 11, 1번노드의 값은 11보다 작으므로,
임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
조건에 해당이 되지 않는다.
왜냐하면 루트노드 7번의 오른쪽 서브트리가 2번 1번이라면, 2번은 x값이 커서 참이지만, 1번은 7번의x값보다 작기 때문이다.
고로, 이 문제의 핵심은 내가 넣은 노드의 바로 위의 부모노드와 x값이 비교가 아닌, 내 위에 있는 전체 부모의 노드의 x값과 전부 비교를 해야한다는 말이다.
문제의 핵심을 파악했다면, 이제 코드로 구현을 들어가보자
우선 Node를 만들기 위해 Node Struct를 만들어줬다.
struct Node{
int x;
int y;
int num;
Node * left;
Node * right;
Node(int X, int Y , int Num) : x(X),y(Y),num(Num), left(NULL),right(NULL) {}
};그다음 노드를 만들었다면, 노드를 연결할 tree를 만들어야 할 것이다.
트리를 만드려면 어떻게해야할까? 당연히 부모와 자식이 있어야한다.
부모와 자식은 어떻게 설정할까?
세로축으로 더 높은게 부모 더 낮은게 자식으로 설정하면 된다.
그러나, 우리는 왼쪽 하위트리는 전부다 자신보다 작아야하고, 오른쪽 하위트리는 전부 다 자신보다 커야하는 조건이 있으므로,
x값의 순서대로 배치하는게 필요하다.
고로, 원하는 Node순서가 7,4,2,6,1,3,9,8,5 순서대로 만드는것이다.
for(int i=0;i<nodeinfo.size();i++){
int x = nodeinfo[i][0];
int y = nodeinfo[i][1];
int nodeIdx = i+1;
v.push_back(Node(x,y,nodeIdx));
}
sort(v.begin(),v.end(),cmp);그렇다면 노드를 만들고, sort를 해주자.
bool cmp
bool cmp(Node A, Node B){
//조건 1. 층수비교
//조건 2. x값 비교
int Astage = A.y;
int Bstage = B.y;
int Ax = A.x;
int Bx = B.x;
if(Astage>=Bstage){
if(Astage == Bstage){
if(Ax>Bx){
return false;
}
}
return true;
}
return false;
}우선 층수를 비교한다.
층수가 만약에 낮으면 false를 return하여 뒤로 보내야한다.
그런데 만약 층수가 크거나 같으면, 같을때를 비교해야한다.
같은데 만약 x값이 더 크다면 false를 return하여 뒤로 보낸다.
만약에 애초에 층수가 컷다면 두번째 if문을 들어가지 않았으므로 return true를 해준다.
이렇게하면 vector < Node>v에 우리가 원한대로 7,4,2,6,1,3,9,8,5 가 순서대로 들어가 있을 것이다.
그 다음엔 맨처음에서 트리를 만들때 소개한대로, 조건에 맞춰서 트리를 완성해야한다.
결국, 이 문제의 핵심은 바로 위의 노드 뿐만아니라, 자신의 위에 있는 모든 노드가 자신보다 전부 크거나, 혹은 자신보다 전부 작음을 보장해야한다.
이를 위해서 재귀함수를 사용할 것이다.
만약에 이그림에서 6보다 x값이 작은 새로운 노드 11이 들어온다고 가정해보자.
4번노드까지와서 비교를 할라 하는데 11이 4번노드의 x보다 작다.
그렇다고 이미 6번노드가 연결되어있는데 6번노드를 무시하고 4번노드와 연결하면 되겠는가? 상식적으로 그건 말이 안된다.
그러면, 다시 6번노드를 불러서 6번노드와 비교하는 것이다. 6번노드보다 작으면 6번노드 왼쪽에, 6번노드보다 크면, 오른쪽에 넣는것이다.
이렇게하면, 7번노드부터 떨어져서 6번노드까지 와서 조건을 검사하는것이므로, 부모노드보다 전부 작거나 큼이 보장이 된다.
makeTree
void makeTree(Node * Root, Node * Child){
if(Root->x > Child -> x){
if(Root->left == NULL){
Root->left = Child;
return;
}
makeTree(Root->left,Child);
}
if(Root->x < Child->x){
if(Root->right == NULL){
Root->right = Child;
return;
}
makeTree(Root->right,Child);
}
}preOrder
preOrder는 간단하게, vector에 넣은다음에 왼쪽끝까지 이동후 오른쪽 끝까지 이동하는 방식으로 설계했다.
void preOrder(Node * Root,vector<int> & v){
v.push_back(Root->num);
if(Root->left !=NULL){
preOrder(Root->left,v);
}
if(Root->right != NULL){
preOrder(Root->right,v);
}
}PostOrder
postOrder는 preOrder와는 다르게, 무작정 넣는것이 아니라
왼쪽 자식도 없고 오른쪽 자식도 없는 경우,
혹은 이미 왼쪽 트리와 오른쪽 트리를 전부 방문한 경우에 vector에 넣어줬다.
void postOrder(Node * Root,vector<int> & v){
if(Root->left !=NULL){
postOrder(Root->left,v);
}
if(Root->right != NULL){
postOrder(Root->right,v);
}
v.push_back(Root->num);
}전체코드
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node{
int x;
int y;
int num;
Node * left;
Node * right;
Node(int X, int Y , int Num) : x(X),y(Y),num(Num), left(NULL),right(NULL) {}
};
bool cmp(Node A, Node B){
//조건 1. 층수비교
//조건 2. x값 비교
int Astage = A.y;
int Bstage = B.y;
int Ax = A.x;
int Bx = B.x;
if(Astage>=Bstage){
if(Astage == Bstage){
if(Ax>Bx){
return false;
}
}
return true;
}
return false;
}
void makeTree(Node * Root, Node * Child){
if(Root->x > Child -> x){
if(Root->left == NULL){
Root->left = Child;
return;
}
makeTree(Root->left,Child);
}
if(Root->x < Child->x){
if(Root->right == NULL){
Root->right = Child;
return;
}
makeTree(Root->right,Child);
}
}
void preOrder(Node * Root,vector<int> & v){
v.push_back(Root->num);
if(Root->left !=NULL){
preOrder(Root->left,v);
}
if(Root->right != NULL){
preOrder(Root->right,v);
}
}
void postOrder(Node * Root,vector<int> & v){
if(Root->left !=NULL){
postOrder(Root->left,v);
}
if(Root->right != NULL){
postOrder(Root->right,v);
}
v.push_back(Root->num);
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
vector<vector<int>> tmp;
vector<Node> v;
for(int i=0;i<nodeinfo.size();i++){
int x = nodeinfo[i][0];
int y = nodeinfo[i][1];
int nodeIdx = i+1;
v.push_back(Node(x,y,nodeIdx));
}
sort(v.begin(),v.end(),cmp);
for(int i=1;i<v.size();i++){
makeTree(&v[0], &v[i]);
}
vector<int>pre;
preOrder(&v[0],pre);
vector<int>post;
postOrder(&v[0],post);
tmp.push_back(pre);
tmp.push_back(post);
return tmp;
}참고
참고를 하고 풀었다. 카카오 LV3는 역시 어렵다
