백준 9252) LCS 2

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

9252번: LCS 2

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

 

---

https://code.plus/course/52

코딩 테스트 준비 - 연습

[백준 온라인 강의 문제 풀이 발췌]

 

 

문제 이해

 

LCS가 무엇인지 알아야 접근할 수 있는 문제이다.

만약 LCS에 대해 잘 모르거나 헷갈린다면 아래의 포스팅된 글을 참조하면 좋을 듯 하다. 

 

https://minoflower.tistory.com/13

백준 9251) LCS

 

 

LCS 문제와 달리 LCS의 길이 뿐만 아니라 LCS를 출력해줘야 한다.

우리는 보통 최종적인 값을 구하면서 동시에 그 값으로부터 정답이 되는 무언가를 출력할 때가 있다.

예를 들면 그래프 탐색 문제에서 최단 경로의 크기를 구하되, 최단 경로를 출력하는 것이다.

 

항상 이런 문제를 접할 때는 역추적을 떠올려주자.

끝에서부터 정답이 되는 순간을 배열 또는 리스트에 마킹해서 정답을 도출하는 기법이다.

 

 

 

접근 방법

 

역추적을 이용하기 위해 먼저 배열을 선언해준다. v : Array<IntArray>

그리고 LCS를 구할 때 3가지의 조건이 있었다.

 

1. str1[i] == str2[j], D[i][j] = D[i-1][j-1] + 1

문자가 같을 경우 이전까지 구한 문자열의 LCS에 +1 을 해줬으므로

이를 표시하기 위해 v[i][j] = 1 로 마킹해준다.

 

 

str1[i] != str2[j], D[i][j] = maxOf(D[i-1][j], D[i][j-1])

 

2. D[i-1][j] < D[i][j-1]

D[i][j-1]이 더 큰 것을 D[i][j] 에 저장하는 꼴임을 표시하기 위해

v[i][j] = 2 로 마킹해준다.

 

3. D[i-1][j] > D[i][j-1]

D[i-1][j]이 더 큰 것을 D[i][j] 에 저장하는 꼴임을 푝시하기 위해

v[i][j] = 3 으로 마킹해준다.

 

 

위의 정보를 토대로 역추적을 하면 된다.

al = str1.length, bl = str2.length 라 했을 때

 

v[al][bl] == 1 이라면 str1 또는 str2를 기준으로(str1로 기준을 잡겠다.)

str1[al-1] 값을 정답에 저장한 후, al - 1, bl - 1 을 해준다. 그래야 이전으로 돌아가기 때문이다.

 

v[al][bl] == 2 라면,

D[i-1][j] < D[i][j-1] 조건이었으므로 j-1 일 때 최대였기 때문에 즉, bl - 1 을 해준다.

 

v[al][bl] == 3 이라면,

D[i-1][j] > D[i][j-1] 조건이었으므로 i-1 일 때 최대였기 때문에 즉, al - 1 을 해준다.

 

 

 

마지막으로 LCS의 길이가 0이라면 문자열을 출력하지 않으므로

 

println(dp[al][bl])
if(dp[al][bl] == 0) return

 

다음과 같이 방호 코드를 작성해주면 된다.

 

 

 

소스 코드

 

fun main() = with(System.`in`.bufferedReader()) {
    val a = readLine()
    val b = readLine()
    val dp = Array(1001) { IntArray(1001)}
    val v = Array(1001) { IntArray(1001)}
    var al = a.length
    var bl = b.length
    for(i in 1..al) {
        for(j in 1..bl) {
            if(a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1
                v[i][j] = 1
            } else {
                v[i][j] = if(dp[i-1][j] < dp[i][j-1]) 2 else 3
                dp[i][j] = maxOf(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    println(dp[al][bl])
    if(dp[al][bl] == 0) return

    val ans = StringBuilder()
    while (al > 0 && bl > 0) {
        when(v[al][bl]) {
            1 -> {
                ans.append(a[al - 1])
                al--
                bl--
            }
            2 -> bl--
            3 -> al--
        }
    }
    println(ans.reverse())
}