[백준] 1120번 문자열(브루트포스 - 완전탐색)[Kotlin - 코틀린]

백준 1120번 문제입니다. (solved.ac) 기준 실버 4 문제입니다.

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

1120번: 문자열

문제

문제 접근

문자열 a, b를 입력받고 두 문자열의 인덱스간 차이의 최소를 구하는 문제입니다.

길이가 같을 경우에는 단순 문자열들의 인덱스를 비교해서 차이를 구하면 되지만 문자열의 길이가 다를 경우에는 두 문자열의 길이를 맞춰주어야합니다.(단, 길이가 다를 경우 a의 길이가 무조건 b보다 작음)

 

길이가 다를 경우 길이를 맞추기 위하여 짧은 문자열의 앞, 뒤 중 자유롭게 문자를 집어넣을 수 있습니다. 문자열의 차이를 최소로 만들어야 하는 문제이므로, 절대 문자인 '*'를 추가하도록 하였습니다. 절대 문자는 무조건 대응하는 문자와 같다고 판단할 문자입니다. - ex) * == a, * == b

 

a와 b의 길이차를 구하고 해당 차이만큼 '*'를 앞뒤로 추가해 줄 수 있습니다. 문자열 a, b의 크기가 50이하 이므로 완전탐색을 통하여 모든 경우의 수를 구하여도 시간이 충분하다고 판단하여 완전탐색으로 구하였습니다.

완전탐색으로 *를 추가한 모든 newA(b와 길이가 같게된 a)를 구하여 그 중 차이가 최소가 될 수 있는 값을 구하도록 하였습니다. 

예를 들어 a = 123, b = 412356일 경우, newA는 123***, *123**, **123*, ***123 이 될 수 있습니다.

정답 코드

fun main() {

    val (a, b) = readln().split(" ")

    var answer = 100
    val lengthA = a.length
    val lengthB = b.length

    // 길이가 같을 때
    if (lengthA == lengthB) {
        answer = difCnt(a, b)
    }

    // 길이가 다를 때
    else {

        var toAddCnt = lengthB - lengthA

        // 부족한 문자의 개수만큼 *을 끼워넣는 과정
        for (index in 0..toAddCnt) {
            
            var newA = ""
            
            for (addFront in 0 until index) {
                newA += "*"
            }
            
            newA += a
            
            for (addBack in 0 until toAddCnt - index) {
                newA += "*"
            }
            
            val difCnt = difCnt(newA, b)
            if (difCnt < answer) answer = difCnt
        }
        
    }

    println(answer)

}

// 두 문자열의 차이를 계산하는 과정
fun difCnt(a: String, b: String): Int {
    var difCnt = 0
    for (index in 0 until a.length) {
        if (a[index] != b[index]
            && a[index] != '*'
        ) difCnt++
    }
    return difCnt
}