백준 5052번 코틀린

반례 찾아보려고 검색해봤더니 이 문제는 코틀린 코드가 인터넷에 하나도 없길래 저라도 올려봅니다.

굉장히 근본없는 풀이방법일 가능성이 높으니 참고용으로만 쓰시길...

 

112 이렇게 되어있는 전화번호를 1,1,2로 자른 후에 트리 형태로 저장하고,

1126을 저장할 때 기존에 1,1,2가 저장된 게 있으니 순서대로 따라가다가 마지막 2에서 해당 노드가 leaf 노드라는 말은 앞에서 1,1,2로 끝나는 번호가 있었다는 말이므로 NO를 출력하고 탐색을 종료합니다.

 

반대로 만약 1126이 먼저 들어오고 112가 나중에 들어온 경우에도 NO를 출력하고 탐색을 종료합니다. (이땐 1,1,2,6에서 2는 leaf가 아니지만 1,1,2를 넣을 때 2번이 leaf이므로 탐색이 종료됩니다.)

 

참고로 112가 있어도 3112때는 NO가 되지 않습니다. 문제에서 접두어일 때만이라는 조건이 있기 때문에 112가 앞에 있어도 3112는 괜찮습니다.

 

data class Node(val index: Int, val isLeaf: Boolean) {
    private val children = ArrayList<Node>()

    fun addChild(index: Int, isLeaf: Boolean): Node? {
        for (c in children) {
            if (c.index == index) {
                if (c.isLeaf || isLeaf) return (null) else (return c) // c.isLeaf만 true -> 112 이후 1126이 들어온 경우 / isLeaf만 true -> 1126 이후 112가 들어온 경우
            }
        }

        // 처음 추가된 index면 children에 추가
        val newNode = Node(index, isLeaf)
        children.add(newNode)
        return newNode
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        solve()
    }
}

fun solve() {
    // 인풋
    val n = readLine()!!.toInt()
    val lines = ArrayList<String>(n)
    repeat(n) {
        lines.add(readLine()!!)
    }

    // 구현
    val tree = Node(-1, false)
    repeat(n) { k ->
        val number = lines[k].toCharArray().map { it.digitToInt() }

        var currentNode: Node? = tree
        for (i in number.indices) {
            currentNode = currentNode?.addChild(number[i], i == number.lastIndex)
            if (currentNode == null) {
                println("NO")
                return
            }
        }
    }
    println("YES")
}

 

처음엔 단순히 String 형태로 배열에 다 집어넣고 일일이 비교했더니 시간 초과나서 결국 트리 형태로 구현하였습니다.