[백준] 알 수 없는 문장 (1099)(kotlin)

문제 설명

입력 및 출력

» 입력

첫째 줄에 문장이 주어진다. 문장의 길이는 최대 50이다. 둘째 줄에 단어의 개수 N이 주어지며, N은 50보다 작거나 같은 자연수이다. 셋째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 50이다. 문장과 단어는 알파벳 소문자로만 이루어져 있다.

» 출력

첫째 줄에 문제의 정답을 출력한다. 만약 문장을 해석할 수 없다면 -1을 출력한다.

예제 입출력(테스트케이스)

입력	출력
neotowheret 4 one two three there	8

문제 풀이1

풀이 참고

import kotlin.math.min

var N = 0
var word = ""
var dp = intArrayOf()
val dictionary = ArrayList<String>()

fun main() {
    input()
    println(getDP(0))
}

fun input() = with(System.`in`.bufferedReader()) {
    word = readLine()
    N = readLine().toInt()
    dp = IntArray(word.length) { 1_000 }
    repeat(N) {
        dictionary.add(readLine())
    }
}

fun partitionWord(targetWord: String): ArrayList<String> {
    val ret = ArrayList<String>(targetWord.length)
    repeat(targetWord.length) { idx ->
        ret.add(targetWord.substring(idx, targetWord.length))
    }
    return ret
}

fun getDP(idx: Int): Int {
    if (idx == word.length) {
        return if (dp[word.length - 1] == 1_000) -1
        else dp[word.length - 1]
    }

    val partitionWordList = partitionWord(word.substring(0, idx + 1))
    for (from in partitionWordList.indices) {
        val shuffleWord = partitionWordList[from]
        for (j in dictionary.indices) {
            val originWord = dictionary[j]

            if (!compareWord(shuffleWord, originWord)) continue

            val cost = calculateCost(shuffleWord, originWord)

            if (from - 1 < 0) {
                dp[idx] = min(dp[idx], cost)
                continue
            }

            dp[idx] = min(cost + dp[from - 1], dp[idx])
        }
    }

    return getDP(idx + 1)
}

fun compareWord(str1: String, str2: String): Boolean {
    if (str1.length != str2.length) return false

    val check = IntArray(26)
    for (i in str1.indices) {
        check[str1[i] - 'a']++
        check[str2[i] - 'a']--
    }

    if (check.any { it != 0 }) return false

    return true
}

fun calculateCost(str1: String, str2: String): Int {
    var ret = 0
    for (i in str1.indices) {
        if (str1[i] != str2[i]) ret++
    }
    return ret
}