백준 14725번
https://www.acmicpc.net/problem/14725
트라이의 자료 구조를 알아야 풀 수 있는 문제라고 한다..
어려워서 다른 분들의 풀이를 참고해서 풀었다
Comparator 구현체를 만들어서 sortWith()
메소드를 사용해서 정렬을 한번 해보았다
import java.io.*
import java.util.*
// input
private lateinit var br: BufferedReader
// variables
private const val FLOOR = "--"
private var N = 0
private var K = 0
private var ans = StringBuilder()
private data class Trie(var name: String, var edge: ArrayList<Trie>)
fun main() {
br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.`out`))
val sb = StringBuilder()
input()
solve()
bw.write(ans.toString())
bw.close()
} // End of main
private fun DFS(trie: Trie, depth: Int) {
val comp = object : Comparator<Trie> {
override fun compare(o1: Trie?, o2: Trie?): Int {
return o1!!.name.compareTo(o2!!.name)
}
}
trie.edge.sortWith(comp)
if (depth != -1) {
for (i in 0 until depth) {
ans.append(FLOOR)
}
ans.append(trie.name).append('\n')
}
trie.edge.forEach {
DFS(it, depth + 1)
}
} // End of ansPrint
private fun solve() {
var trie = Trie("", ArrayList())
var node: Trie
while (N-- > 0) {
val st = StringTokenizer(br.readLine())
K = st.nextToken().toInt()
node = trie
while (K-- > 0) {
var name = st.nextToken()
var idx = -1
var size = node.edge.size
for (i in 0 until size) {
if (node.edge[i].name == name) {
idx = i
break
}
}
if (idx == -1) {
node.edge.add(Trie(name, ArrayList()))
node = node.edge[node.edge.size - 1]
} else {
node = node.edge[idx]
}
}
}
DFS(trie, -1)
} // End of solve
private fun input() {
N = br.readLine().toInt()
} // End of input