[백준/BOJ] 9252번: LCS 2

문제

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

9252번: LCS 2

해설

문제의 예시를 보자.

ACAYKP, CAPCAK 두 문장이 있다.

여기서 부분 수열이 되는 수열 중 가장 긴 것은 ACAK이다.

이를 찾아가는 과정을 보자.

 

우선 2차원 배열을 선언할 것이다.

dp라는 이름을 가진 배열이라 하자.

각 인덱스의 값을 정할 때, 

• str1[i] == str2[j]라면 부분 수열이 되는 값이 하나 늘은 것이므로 dp[i-1][j-1] + 1의 값을 갖게 된다.
• 같지 않다면, dp[i-1][j]와 dp[i][j-1] 중 더 큰 값이 더 긴 부분 수열을 의미하므로 더 큰 값을 갖게 된다.

이 과정을 통해 dp[str1.size][str2.size]에 도착한다면, 두 문장에서 얻을 수 있는 가장 긴 부분 순열의 길이를 구할 수 있다.

즉 예제에서는 길이가 4인 부분 수열이 가장 긴 부분 수열이라는 것을 알 수 있다.

 

이제 어떠한 문자들로 가장 긴 부분 수열이 이루어져 있는지를 알아내야 한다.

 이때의 규칙은 다음과 같다.

• dp[i][j] == dp[i][j-1]이라면 그 전이랑 지금이랑 다를게 없다는 것이므로 부분 증가 수열이 같다는 말이다. 따라서 j를 줄여 다시 비교해볼 것이다.
• dp[i][j] == dp[i-1][j]는 위와 같은 맥락이다. 이때는 i를 줄여준다.
• 위 둘에 모두 해당하지 않는다면, 공통 부분 순열이 늘어났다는 것을 알 수 있다. 즉 dp[i][j]가 최장 공통 부분 순열의 구성 알파벳이 되는 것이다. 이를 Stack에 담고, 다음 부분 증가 순열의 구성 알파벳을 찾기 위해 i와 j를 모두 줄여준다.

이렇게 해서 모든 구성 알파벳을 Stack에 쌓았다면, 차례로 pop하여 출력해주면 된다.

코드

import java.util.*
import kotlin.math.max

private lateinit var dp: Array<IntArray>
private val sb = StringBuilder()

fun main() = with(System.`in`.bufferedReader()) {
    val str1 = readLine().toCharArray()
    val str2 = readLine().toCharArray()

    val len1 = str1.size
    val len2 = str2.size
    dp = Array(len1 + 1) { IntArray(len2 + 1) }

    lcs(str1, str2)
    printString(str1, len1, len2)

    println(sb.toString())
}

private fun lcs(str1: CharArray, str2: CharArray) {
    for(i in 1 .. str1.size) {
        for(j in 1 .. str2.size) {
            if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1] + 1
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        }
    }

    sb.append("${dp[str1.size][str2.size]}\n")
}

private fun printString(str: CharArray, len1: Int, len2: Int) {
    val stack = Stack<Char>()
    var i = len1
    var j = len2

    while(dp[i][j] != 0) {
        if(dp[i][j] == dp[i][j-1]) j--
        else if(dp[i][j] == dp[i-1][j]) i--
        else if(dp[i][j] - 1 == dp[i-1][j-1]) {
            stack.push(str[i-1])
            i--
            j--
        }
    }

    while(stack.isNotEmpty()) {
        sb.append(stack.pop())
    }
}