728x90
문제설명
풀이방법
해당 문제를 풀기 위해서는 이진트리의 순회방법을 살펴볼 필요가 있다.
- 전위순회(preOrder) : 루트(root) 방문 -> 왼쪽 자식노드 -> 오른쪽 자식노드
- 중위순회(inOrder) : 왼쪽 자식노드 방문 -> 루트(root) -> 오른쪽 자식노드
- 후위순회(postOrder) : 왼쪽 자식노드 방문 -> 오른쪽 자식노드 -> 루트(root)
-> 순회방법의 앞글자인 전, 중, 후는 각각 루트노드의 방문 순서를 나타냄
문제의 조건인, '자식의 y값은 부모의 y값보다 작다'이므로 y값이 큰 순서대로 트리에 삽입이므로 정렬
구현코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
import java.util.*;
class Solution {
int[][] answer = {};
int idx;
public int[][] solution(int[][] nodeinfo) {
Node node[]=new Node[nodeinfo.length];
for(int i=0;i<nodeinfo.length;i++){
node[i]=new Node(nodeinfo[i][0],nodeinfo[i][1],i+1,null,null);
}
Arrays.sort(node, new Comparator<Node>(){
public int compare(Node n1, Node n2){
if(n1.y==n2.y) return n1.x-n2.x;
else return n2.y-n1.y;
}
});
Node root=node[0];
for(int i=1;i<node.length;i++){
insertNode(root,node[i]);
}
answer=new int[2][node.length];
idx=0;
preOrder(root);
idx=0;
postOrder(root);
return answer;
}
public void preOrder(Node root){
if(root!=null){
answer[0][idx++]=root.value;
preOrder(root.left);
preOrder(root.right);
}
}
public void postOrder(Node root){
if(root!=null){
postOrder(root.left);
postOrder(root.right);
answer[1][idx++]=root.value;
}
}
public void insertNode(Node parent, Node child){
if(parent.x>child.x){
if(parent.left==null){
parent.left=child;
}
else insertNode(parent.left,child);
}
else {
if(parent.right==null){
parent.right=child;
}
else insertNode(parent.right,child);
}
}
public class Node{
int x;
int y;
int value;
Node left;
Node right;
public Node(int x, int y, int value, Node left, Node right){
this.x=x;
this.y=y;
this.value=value;
this.left=left;
this.right=right;
}
}
}
|
728x90
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 스킬트리 (0) | 2023.09.27 |
|---|---|
| [프로그래머스] 파일명 정렬 (0) | 2022.05.10 |
| [프로그래머스] 섬 연결하기 (0) | 2022.05.04 |
| [프로그래머스] 행렬의 곱셈 (0) | 2022.04.30 |
| [프로그래머스] N개의 최소공배수 (0) | 2022.04.30 |
