(BOJ) 1230 문자열 거리

1230 문자열 거리

• 분류 : 다이나믹 프로그래밍

문제

문자열 O에서 문자열 N까지 문자열 거리는 O를 N과 같게 만들기 위해 필요한 문자열 삽입의 최솟값

이다. 문자열 삽입은 O의 어느 위치에서건 가능하다.

예를 들어, O가 “gosrl”일 때, ”sip gi”을 r이전에 삽입한다면 “gossip girl“이 된다.

문자열 O와 문자열 N이 주어질 때, 두 문자열의 거리를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 O, 둘째 줄에 문자열 N이 주어진다.

문자열의 길이는 최대 1,000이다.

문자열은 아스키 코드의 값이 32보다 크거나 같고, 126보다 작거나 같은 문자로만 이루어져 있다.

출력

첫째 줄에 문자열 O와 문자열 N의 문자열 거리를 출력한다. 만약 O를 N으로 만들 수 없다면 -1을 출력한다.

예제 입력 1

hello fine
hello, how are you? I'm fine thank you and you?

예제 출력 1

2

예제 입력 2

aaaaa
ababababa

예제 출력 2

4

예제 입력 3

no way
No way!

예제 출력 3

-1

예제 입력 4

abcefijklmnopuvwxz
abcdefghijklmnopqrstuvwxyz

예제 출력 4

4

Solution

Expander

import java.util.*
import kotlin.math.min

private const val MAX = 1001

private var O: String = ""
private var N: String = ""

private var DP = Array(MAX) {
    Array(MAX) {
        IntArray(2) { 0 }
    }
}

fun main() {
    input()
    init()
    solve()
}

private fun init() {
    DP[0][0][0] = 0
    DP[0][0][1] = MAX
    for (i in 1 .. N.length) {
        DP[0][i][0] = MAX
        DP[0][i][1] = 1
    }
}

private fun input() = with(Scanner(System.`in`)) {
    O = nextLine()
    N = nextLine()
}

private fun solve() {
    // 만약 O를 N으로 만들 수 없다면 -1을 출력한다.
    if (O.length > N.length) {
        println(-1)
        return
    }

    for (i in 0 until O.length) {
        for (j in 0 .. i) {
            DP[i + 1][j][0] = MAX
            DP[i + 1][j][1] = MAX
        }

        for (j in i until N.length) {
            if (O[i] == N[j]) {
                DP[i + 1][j + 1][0] = min(DP[i][j][0], DP[i][j][1])
            } else {
                DP[i + 1][j + 1][0] = MAX
            }
            DP[i +1][j + 1][1] = min(DP[i + 1][j][0] + 1, DP[i + 1][j][1])
        }
    }

    val result = min(DP[O.length][N.length][0], DP[O.length][N.length][1])
    if (result >= MAX) {
        println(-1)
    } else {
        println(result)
    }
}

Point of Thinking

• 문자열 O를 split해서 동일한 문자열을 치환해 나간 뒤, 이를 중복 제거한 다음 합계를 구하면 답이 나올 것이라고 생각했다.
• 하지만 입력값의 범위가 아스키 코드 32 ~ 126이므로 치환 방법은 사용할 수가 없고, 결국 동적계획법으로 풀이해야 한다.
• 문자열 양극 혹은 내부에 문자열을 넣는 것이므로, 넣을 수 있냐 없냐에 따라 최솟값을 갱신해나가는 식으로 처리해야 한다.
• 문자열 길이가 1000자라서 모든 문자를 순회하는 식으로 점화식을 짰는데 다행히 Accepted되었다.
• 메모리 이슈가 있긴 했는데 Integer를 Short로 치환했다가, 로직을 개선해서 다시 Integer로 Accepted.