백준 14725 개미굴 Kotlin

: ) YOUNG·2023년 7월 12일
1

알고리즘

목록 보기
225/417
post-thumbnail

백준 14725번
https://www.acmicpc.net/problem/14725

문제




생각하기


  • 트라이의 자료 구조를 알아야 풀 수 있는 문제라고 한다..

  • 어려워서 다른 분들의 풀이를 참고해서 풀었다

  • Comparator 구현체를 만들어서 sortWith() 메소드를 사용해서 정렬을 한번 해보았다

    • 시간적 효율은 그닥...

동작



코드


Kotlin


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

0개의 댓글