7432번: 디스크 트리

문제 출처 : https://www.acmicpc.net/problem/7432

 

언어 : Kotlin

 

문제 설명 :

갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파일이 걱정되기 시작했다. 다행히 상근이는 저장되어 있는 중요한 디렉토리의 전체 경로를 텍스트 파일로 따로 저장하고 있었다. 예를 들면, WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86. 

상근이의 중요한 디렉토리의 전체 경로가 모두 주어졌을 때, 디렉토리 구조를 구해 보기 좋게 출력하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 중요한 디렉토리 전체 경로의 개수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개 줄에는 디렉토리 경로가 주어진다. 경로는 한 줄로 이루어져 있으며, 공백을 포함하지 않는다. 경로는 80글자를 넘지 않으며, 디렉토리는 역슬래시(\)로 구분된다.

각 디렉토리의 이름은 1~8글자이며, 알파벳 대문자, 숫자, 특수 문자로 이루어져 있다. 디렉토리 이름에 들어있을 수 있는 특수문자는 !#$%&'()-@^_`{}~ 이다.

 

출력 :

디렉토리 구조를 보기 좋게 출력한다. 한 줄에 하나씩 디렉토리의 이름을 출력하며, 공백은 디렉토리 구조상에서 깊이를 의미한다. 각 서브 디렉토리는 사전순으로 출력해야 하며, 부모 디렉토리에서 출력한 공백의 개수보다 1개 많게 공백을 출력한다. 예제 출력을 보면서 형식을 참고하는 것이 좋다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
7 WINNT\SYSTEM32\CONFIG GAMES WINNT\DRIVERS HOME WIN\SOFT GAMES\DRIVERS WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86	GAMES  DRIVERS HOME WIN  SOFT WINNT  DRIVERS  SYSTEM32   CERTSRV    CERTCO~1     X86   CONFIG

 

풀이 : 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    val trie = Trie()
    for (i in 0 until n) {
        trie.insert(readLine())
    }

    trie.print(0, bw)
    bw.flush()
    bw.close()
}

class Trie(private val root: TrieNode = TrieNode()) {
    fun insert(key: String) {
        var cur = root
        val address = key.split("\\")

        for (f in address) {
            cur.childNode.putIfAbsent(f, TrieNode())
            cur = cur.childNode[f]!!
        }
    }

    fun print(depth: Int, bw: BufferedWriter) {
        printing(root, depth, bw)
    }

    private fun printing(cur: TrieNode?, depth: Int, bw: BufferedWriter) {
        ArrayList(cur!!.childNode.keys).sorted().forEach {
            bw.append(" ".repeat(depth)).appendLine(it)
            printing(cur.childNode[it], depth + 1, bw)
        }
    }
}

class TrieNode {
    val childNode: MutableMap<String, TrieNode> = hashMapOf()
}