문제
https://school.programmers.co.kr/learn/courses/30/lessons/42892
입력
int배열 형태로 구성된 node 정보
[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]출력
이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때,
노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return
풀이
제한조건
- nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
- nodeinfo의 길이는 1 이상 10,000 이하이다.
- nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
- 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
- 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
- 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.
접근방법
Tree 자료구조를 이용한 문제이다.
LinkedList, Tree 자료형에 대해 한 번쯤 구현해봤다면 또는 해당 자료형에 대한 이해가 있다면 생각보다 쉽게 풀 수 있다.
일단 문제에서 주어진 특별한 규칙을 알아야한다.
- 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
- 모든 노드는 서로 다른 x값을 가진다.
- 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
- 자식 노드의 y 값은 항상 부모 노드보다 작다.
- 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
- 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.우선 입력 정보를 Node 형식으로 만들고, 편의를 위해서 정렬해보자.
정렬 기준은 Y가 큰 순서대로 정렬한다.
( Y가 큰 값이 Root와 가까운 노드이므로 )
X에 대한 정렬은 필요없다.
이제 주어진 내용을 바탕으로 Node 구현체를 만들어보자.
class Node implements Comparable<Node>{
int num;
int x;
int y;
Node left;
Node right;
Node(int n, int x, int y){
num = n;
this.x = x;
this.y = y;
left = null;
right = null;
}
public int compareTo(Node o){
if(this.y == o.y)
return this.x - o.x;
return o.y - this.y;
}
}이제 Node를 만들었으니, 이제 Tree 구조를 잡아보자.
Tree 구조를 만들때 위에서 언급한 특별한 규칙을 기반으로 만들어야 한다.
class BTree{
Node head;
BTree(){
head = null;
}
void insert(Node inNode){
// head가 없다면 head에 넣는다.
if(head == null){
head = inNode;
return;
}
// head가 있다면, x좌표에 따라 왼쪽 또는 오른쪽 자식인지 결정된다.
if(inNode.x < head.x){
// left가 null이면 left 자리에 들어간다.
if(head.left == null)
head.left = inNode;
else // null이 아니면, 해당 Node의 Left를 기준으로 다시 insert를 시도한다.
insert(head.left, inNode);
}else{
if(head.right == null)
head.right = inNode;
else
insert(head.right, inNode);
}
}
void insert(Node base, Node inNode){
if(inNode.x < base.x){
if(base.left == null)
base.left = inNode;
else
insert(base.left, inNode);
}else{
if(base.right == null)
base.right = inNode;
else
insert(base.right, inNode);
}
}
}특별한 규칙에 따라 데이터 삽입을 완료했다.
이제 순회를 해보자.
전위 순회는 VLR 순, 후위 순회는 LRV 순서로 순회한다.
해당 하는 함수를 만들어보자.
단순 출력하는 것이 아니라, 순서를 담아야하므로 List형태를 사용했다.
// VLR 순으로 탐색한다.
List<Integer> getPreorder(){
List<Integer> list = new ArrayList();
preorder(head, list);
return list;
}
void preorder(Node n, List l){
l.add(n.num); // 현재 노드의 번호
if(n.left != null) // 왼쪽이 있다면
preorder(n.left, l); // 왼쪽 탐색
if(n.right != null) // 오른쪽이 있다면
preorder(n.right, l); // 오른쪽 탐색
}
// LRV 순으로 탐색한다.
List<Integer> getPostorder(){
List<Integer> list = new ArrayList();
postorder(head, list);
return list;
}
void postorder(Node n, List l){
if(n.left != null) // 왼쪽이 있다면
postorder(n.left, l); // 왼쪽 탐색
if(n.right != null) // 오른쪽이 있다면
postorder(n.right, l); // 오른쪽 탐색
l.add(n.num); // 현재 노드의 번호
}이제 List형태의 결과를 모두 구했으므로, 문제에서 원하는 대로 2차원 배열형태로 값을 변환해서 Return한다.
코드
import java.util.*;
class Node implements Comparable<Node>{
int num;
int x;
int y;
Node left;
Node right;
Node(int n, int x, int y){
num = n;
this.x = x;
this.y = y;
left = null;
right = null;
}
public int compareTo(Node o){
if(this.y == o.y)
return this.x - o.x;
return o.y - this.y;
}
}
class BTree{
Node head;
BTree(){
head = null;
}
void insert(Node inNode){
if(head == null){
head = inNode;
return;
}
if(inNode.x < head.x){
if(head.left == null)
head.left = inNode;
else
insert(head.left, inNode);
}else{
if(head.right == null)
head.right = inNode;
else
insert(head.right, inNode);
}
}
void insert(Node base, Node inNode){
if(inNode.x < base.x){
if(base.left == null)
base.left = inNode;
else
insert(base.left, inNode);
}else{
if(base.right == null)
base.right = inNode;
else
insert(base.right, inNode);
}
}
// VLR 순으로 탐색한다.
List<Integer> getPreorder(){
List<Integer> list = new ArrayList();
preorder(head, list);
return list;
}
void preorder(Node n, List l){
l.add(n.num);
if(n.left != null)
preorder(n.left, l);
if(n.right != null)
preorder(n.right, l);
}
// LRV 순으로 탐색한다.
List<Integer> getPostorder(){
List<Integer> list = new ArrayList();
postorder(head, list);
return list;
}
void postorder(Node n, List l){
if(n.left != null)
postorder(n.left, l);
if(n.right != null)
postorder(n.right, l);
l.add(n.num);
}
}
class Solution {
public int[][] solution(int[][] nodeinfo) {
List<Node> list = new ArrayList();
for(int i = 0 ; i < nodeinfo.length; ++i)
list.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
// y가 크고 x가 작은순으로 정렬했다.
Collections.sort(list);
BTree tree = new BTree();
// 트리에 데이터를 넣자.
for(Node n : list)
tree.insert(n);
List<Integer> preOrderList = tree.getPreorder(); // 전위순회 결과
List<Integer> postOrderList = tree.getPostorder(); // 후위순회 결과
return new int[][] {preOrderList.stream().mapToInt(i->i).toArray(),
postOrderList.stream().mapToInt(i->i).toArray()};
}
}