[백준] 2529번: 부등호 - Kotlin[코틀린]

문제

 

2529번: 부등호

 

---

풀이

 

 부등호를 만족하는 최소와 최대 정수를 백트래킹으로 찾는 문제이다. 입력받은 부등호에 따라 올바른 숫자를 선택하고 재귀적으로 탐색을 진행한다. 가장 먼저 완성된 답이 최소 정수, 가장 나중에 완성된 답이 최대 정수가 되는 것으로 각각 출력해주면 된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val ex = br.readLine().split(' ').map { it }

    var visited = BooleanArray(10)
    val ans = mutableListOf<String>()
    
    fun dfs(start: Int, depth: Int, word: String) {
        if(depth == num) {
            ans.add(word)
            return
        }
        for(i in 0 until 10) {
            if(visited[i]) continue
            if(ex[depth] == ">") {
                if(start > i) {
                    visited[i] = true
                    dfs(i, depth+1, word+i)
                    visited[i] = false
                }
            } else {
                if(start < i) {
                    visited[i] = true
                    dfs(i, depth + 1, word + i)
                    visited[i] = false
                }
            }
        }
    }

    for(i in 0 until 10) {
        visited = BooleanArray(10)
        visited[i] = true
        dfs(i, 0, "$i")
        visited[i] = false
    }

    bw.write("${ans.last()}\n${ans.first()}")
    bw.flush()
    bw.close()
    br.close()
}