[백준] 좋은수열

백트래킹을 통한 재귀구현

이미 완성된 수열의 경우 좋은수열로 판단하여 추가로 들어오는 값에대한 앞과 뒤를 확인하면 된다.

 

fun main() = with(Scanner(System.`in`)) {
    val count = nextInt()

    var result = ""

    fun backTracking(n: Int, str: String, index: Int) {
        if(!canMake(str)){
            return
        }
        if (index == n) {
            if(result.isEmpty()){
                result = str
                return
            }
            for(i in str.indices){
                if(result[i] < str[i]){
                    return
                }

            }
            result = str
            return
        }

        for (i in 1..3) {
            backTracking(n, str + i.toString(), index + 1)
        }
    }
    backTracking(count, "", 0)
    println(result)
}

fun canMake(str: String): Boolean {
    for (i in 1 .. str.length / 2) {
        val start = str.substring(str.length - i * 2, str.length - i)
        val end = str.substring(str.length - i, str.length)
        if(start == end) return false
    }
    return true
}