[백준 2661] - 좋은수열(Kotlin)[골드4]

문제

https://www.acmicpc.net/problem/2661

2661번: 좋은수열

---

문제 풀이

전형적인 백트래킹 문제의 예시라고 할 수 있다.

 

백트래킹에 대해 간단히 얘기하자면 사전적 정의는 되추적 알고리즘이라고 불린다.

결과를 찾는 도중 막히면 다시 되돌아가서 결과를 찾고, 모든 노드를 탐색해서 만드는 DFS와 비슷하다.

DFS와 다른 점은 노드를 탐색하기 전에 특정한 조건을 걸고 해당 조건에 부합하지 않는다면 탐색을 진행하지 않는다.

해당 문제에서 특정한 조건이 이제 인접한 두 개의 부분 수열이 동일한가에 대한 여부라고 생각하면 될 것이다.

 

요약하자면 백트래킹은 DFS를 진행하면서 모든 노드가 아닌 특정한 조건에 부합하는 노드만 탐색한다.

해당 문제에서 특정한 조건은 인접한 두 부분수열이 동일한가!이다.

 

해당 부분이 DFS 함수이다.

만약 평범한 DFS 문제였다면 if(check())를 통해서 조건을 걸지 않고, 모든 노드에 대해 탐색했을 것이다.

이제 백트래킹을 하는 조건에 대한 함수이다.

• 여기서 subStr은 기준문자열이다. 1글자,2글자,3글자 ... 서서히 늘어난다.
• 그러한 기준문자열을 잡고, 그 다음 글자부터 기준문자열만큼의 문자열을 뽑아서 두 개의 문자열이 동일한지 판단해서 만약 같다면 조건에 부합하지 않고, 같지 않다면 탐색을 진행한다.
• 무사히 for 문을 완수했다면 조건에 부합한다는 뜻이다.

 

내가 한가지 놓쳤던 점은 처음으로 solution을 통해서 만들어진 문자열은 최솟값일 수밖에 없다는 뜻이다.

따라서 비교를 하지 않고, 출력하고 종료하는 식으로 구현했다.

 

코드

package BOJ.BackTracking.`2661_좋은수열`.ljh

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.system.exitProcess

class `2661` {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private var n = 0
    private val items = arrayOf("1", "2", "3")
    private var answer = ""

    init {
        n = readln().toInt()
    }

    fun solution(cnt: Int) {
        if (cnt == n) {
            println(answer)
            exitProcess(0)
        } else {
            for (item in items) {
                answer += item
                if (check()) {
                    solution(cnt + 1)
                }
                answer = answer.dropLast(1)
            }
        }
    }

    fun check(): Boolean { //같은 패턴이 있는지 확인을 하는 법.
        if (answer.length == 1)
            return true
        for (j in answer.indices) { // == j until answer.length
            for (i in j..< answer.length) {
                val substr = answer.substring(j..i)
                if (i + 1 >= answer.length || i + substr.length >= answer.length)
                    break
                val mainstr = answer.substring(i + 1..i + substr.length) //i+1부터 i까지 검사
                if (substr == mainstr)
                    return false
            }
        }
        return true
    }
}

fun main() {
    val solution = `2661`()
    solution.solution(0)
}