-
Notifications
You must be signed in to change notification settings - Fork 6
/
Harin.java
186 lines (154 loc) · 5.5 KB
/
Harin.java
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
import java.io.*;
import java.util.*;
public class Harin {
private static Node foundNode;
private static class Node implements Comparable<Node>{
String key;
String data;
ArrayList<Node> children;
int level;
public Node(String key, int level) {
this.key = key;
this.data = null;
this.children = new ArrayList<>();
this.level = level;
}
@Override
public boolean equals(Object o) {
Node node = (Node) o;
if(this.key.equals(node.key)){
return true;
}
return false;
}
@Override
public int hashCode() {
return Objects.hash(key);
}
@Override
public String toString() {
return "Node{" +
"key='" + key + '\'' +
", data='" + data + '\'' +
", level=" + level +
'}';
}
@Override
public int compareTo(Node o) {
return this.level != o.level ? Integer.compare(o.level, this.level) : this.key.compareTo(o.key);
}
public void sortChildren(){
Collections.sort(this.children);
}
}
private static class Tree{
Node root;
public Tree(Node root) {
this.root = root;
}
private Node insert(Node node, String str, int index, int level){
//마지막 글자까지 삽입했으면
if(index == str.length()){
node.data = str; //데이터 입력
return node;
}
//str 한글자씩 자식 노드로 삽입
String key = String.valueOf(str.charAt(index));
Node newNode = new Node(key, level); //레벨은 상위레벨 + 1
//해당 글자가 없다면 새로운 노드로 삽입
if(!node.children.contains(newNode)){
node.children.add(newNode);
}
//해당 글자가 있다면 자식 노드로 다음 글자 삽입
else {
for (int i = 0; i < node.children.size(); i++) {
if (node.children.get(i).equals(newNode)) {
newNode = node.children.get(i);
}
}
}
Node rtrnNode = null;
rtrnNode = insert(newNode, str, index+1, level);
return rtrnNode;
}
private void search(Node node, String str){
if(node.data != null && node.data.equals(str)){
foundNode = node;
return;
}
else if(node.children.isEmpty()){
return;
}
for(int i=0; i<node.children.size(); i++){
search(node.children.get(i), str);
}
}
private void search_children(Node node, String str){
for(int i=0; i<node.children.size(); i++){
search(node.children.get(i), str);
}
}
private void printAnswer(Node node){
if(node.data != null) {
int space = node.level-1;
for(int i=0; i<space; i++) System.out.print(" ");
System.out.println(node.data);
}
if(node.children.isEmpty()) return;
for(int i=0; i<node.children.size(); i++){
printAnswer(node.children.get(i));
}
}
private void sort(Node node){
Collections.sort(node.children);
if(node.children.isEmpty()) return;
for(int i=0; i<node.children.size(); i++){
sort(node.children.get(i));
}
}
private void sort(){
sort(this.root);
}
private static void printNode(Node node){
System.out.println(node);
System.out.println("\t\tchildren : " + node.children);
if(node.children.isEmpty()){
return;
}
for(int i=0; i<node.children.size(); i++){
printNode(node.children.get(i));
}
}
private void printAnswer(){
printAnswer(this.root);
}
private void printNode(){
printNode(this.root);
}
}
public static void main(String[] args) throws IOException {
Node root = new Node(null, 0);
Tree tree = new Tree(root);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++){
StringTokenizer st = new StringTokenizer(br.readLine(), "\\");
Node prevNode = root;
while(st.hasMoreTokens()){
foundNode = null;
String dirname = st.nextToken();
tree.search_children(prevNode, dirname);
//없으면 상위레벨 밑에 이어붙인다
if(foundNode == null){
prevNode = tree.insert(prevNode, dirname, 0, prevNode.level+1);
}
//있으면 현재 디렉토리를 상위로 가르키고 다음 탐색
else{
prevNode = foundNode;
}
}
}
tree.sort();
tree.printAnswer();
}
}