[BOJ] 2661번 : 좋은수열

문제 보기

풀이

백트래킹 문제이며 좋은 수열인지 나쁜 수열인지 검사하는 코드를 구현하는 것이 핵심이다.

문자열에서 동일한 요소의 중복은 요소의 길이가 1 ~ N/2의 범위에 있을 때만 발생한다.

백트래킹을 통해 수열을 늘려나가는 식이므로 맨 뒷자리를 기준으로

맨 뒤 1자리의 수가 그 앞의 1자리 수와 동일한지

맨 뒤 2자리의 수가 그 앞의 2자리 수와 동일한지

맨 뒤 3자리의 수가 그 앞의 3자리 수와 동일한지

맨 뒤 4자리의 수가 그 앞의 4자리 수와 동일한지

…

맨 뒤 N/2자리의 수가 그 앞의 N/2자리 수와 동일한지 비교하는 식으로

한 번이라도 동일한 경우가 발생한다면 그 수열은 나쁜 수열로 판단할 수 있다.

가장 첫 번째로 나오는 백트래킹 알고리즘의 결과가 결과값들 중 가장 작은 수이기 때문에 기본적인 백트래킹 문제들과 같이 만들어진 결과값들끼리 최대나 최소를 비교할 필요가 없다. 그렇기 때문에 프로세스를 종료하는 코드 혹은 플래그를 이용하는 코드가 사용이 된다.

가장 작은 수를 나타내는 수열을 구하는 것이기 때문에 첫 번째 자리는 무조건 1이 나온다. 그러므로 dfs의 첫 탐색 정점 기준을 "1"로 잡고 시작하는 것이 더 효율적인 코드이지만 쉬운 이해를 위해 dfs("")을 사용하였다.

소스

kotlin

import java.util.Scanner
import kotlin.system.exitProcess

var n = 0

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    dfs("") // dfs("1")이 더 효율적
}

fun dfs(s: String) {
    if (s.length == n) {
        println(s)
        exitProcess(0)
    }

    for (i in 1..3) {
        if ((s + i).isGood()) {
            dfs(s + i)
        }
    }
}

fun String.isGood(): Boolean {
    val len = this.length / 2

    for (i in 1..len) {
        if (this.substring(this.length - i) == this.substring(this.length - i * 2, this.length - i))
            return false
    }
    return true
}

자바에서 프로세스를 강제 종료하는 System.exit(0)는 코틀린에선 exitProcess(0)를 사용한다. 하지만 exitProcess(0)를 사용하면 kotlin.system 패키지를 import 해줘야하는 번거로움이 있기에 시간이 제한되고 긴장되는 코딩 테스트 환경에서는 아래 코드와 같이 플래그 변수를 사용하거나 자바의 System.exit(0)를 사용하는 것이 나을 수도 있다.

import java.util.Scanner

var n = 0
var exit = false

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    dfs("")
}

fun dfs(s: String) {
    if (exit) return

    if (s.length == n) {
        println(s)
        exit = true
    }

    for (i in 1..3) {
        if ((s + i).isGood()) {
            dfs(s + i)
        }
    }
}

fun String.isGood(): Boolean {
    val len = this.length / 2

    for (i in 1..len) {
        if (this.substring(this.length - i) == this.substring(this.length - i * 2, this.length - i))
            return false
    }
    return true
}

References

• https://bellog.tistory.com/43