#유형 : 트리, 자료구조
#난이도 : 프로그래머스 LEVEL 3
#입력을 우선순위큐를 사용하여 Y의 크기순, x는 작은순으로 정렬하면 된다. 우선순위큐를 사용해도 되고, 정렬기준을 통해 정렬을 해도 된다. 그러면 가장 앞에 루트노드가 올것이다. 그다음은 이진트리 조건에 따라 left, right를 정해서 트리를 완성하면 된다. 백준을 주로 풀어와서, 프로그래머스 문제는 좀 출력하기가 어색하다. 따라서 코드가 좀 복잡하게 보일 지라도, 기본 알고리즘은 간단하다
|
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
package programmers;
import java.util.ArrayList;
import java.util.PriorityQueue;
public class root {
static No root;
static ArrayList<Integer> re[];
public static void main(String[] args) {
int nodeinfo[][] = {{5,3},{11,5},{13,3},{3,5},{6,1},{1,3},{8,6},{7,2},{2,2}};
int [][]answer = solution(nodeinfo);
for(int i=0; i<2; i++) {
for(int j=0; j<nodeinfo.length; j++)
System.out.print(answer[i][j]+" " );
System.out.println();
}
}
public static int[][] solution(int[][] nodeinfo) {
solve(nodeinfo);
int[][] answer = new int[2][nodeinfo.length];
for(int i=0; i<2; i++) {
for(int j=0; j<nodeinfo.length; j++) {
answer[i][j] = re[i].get(j);
}
}
return answer;
}
public static void solve(int[][] nodeinfo) {
// int[][] answer = {};
re = new ArrayList[2];
for(int i=0; i<2; i++) {
re[i]= new ArrayList<>();
}
PriorityQueue<Node> pq = new PriorityQueue<>();
for(int i=0; i<nodeinfo.length; i++) {
pq.add(new Node(nodeinfo[i][0], nodeinfo[i][1], i+1));
}
Node tmp = pq.poll();
No newNo = new No(tmp.num, tmp.x);
root = newNo;
while(!pq.isEmpty()) {
Node nd = pq.poll();
No n = new No(nd.num, nd.x);
find(root, n);
}
preorder(root);
postorder(root);
}
private static void find(No r, No n) {
// TODO Auto-generated method stub
if(r.x > n.x && r.left != null) {
find(r.left, n);
}else if(r.x > n.x && r.left == null) {
r.left = n;
}else if(r.x < n.x && r.right != null) {
find(r.right, n);
}else {
r.right=n;
}
}
public static void preorder(No n) {
if(n == null) {
return;
}
// System.out.println(n.num);
re[0].add(n.num);
preorder(n.left);
preorder(n.right);
}
public static void postorder(No n) {
if(n == null)
return;
postorder(n.left);
postorder(n.right);
re[1].add(n.num);
}
public static class No{
int num;
int x;
No left;
No right;
public No(int n, int x) {
this.num=n;
this.x=x;
this.left=null;
this.right=null;
}
}
public static class Node implements Comparable<Node>{
int x;
int y;
int num;
public Node(int x, int y, int num) {
this.x=x;
this.y=y;
this.num=num;
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
if(this.y < o.y)
return 1;
else if(this.y == o.y) {
if(this.x > o.x)
return 1;
else
return -1;
}
return -1;
}
}
}
|
cs |
'프로그래머스' 카테고리의 다른 글
| #프로그래머스_[1차] 뉴스 클러스터링 - Java 자바 (0) | 2020.05.28 |
|---|---|
| #프로그래머스_문자열 압축 - Java 자바 (0) | 2020.05.24 |
| #프로그래머스_SQL_String, Date - DATETIME에서 DATE로 형 변환 (0) | 2020.04.28 |
| #프로그래머스_SQL_String, Date - 오랜 기간 보호한 동물(2) (0) | 2020.04.28 |
| #프로그래머스_SQL_String, Date - 중성화 여부 파악하기 (0) | 2020.04.28 |
