[백준 1958] LCS 3

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

✍️ 첫번째 접근

첫번째 문자열과 두번재 문자열에 대한 LCS를 구하고, 그 결과와 세번째 문자열에 대한 LCS를 구하는 접근을 하였다.
하지만, 틀리게 되어 반례가 있나 생각해보았더니 반례가 존재하였다.

import Foundation

let str1 = readLine()!.map { String($0) }
let str2 = readLine()!.map { String($0) }
let str3 = readLine()!.map { String($0) }
var LCS1 = Array(repeating: Array(repeating: 0, count: str2.count+1), count: str1.count+1)
var LCS_str = ""
for i in 1...str1.count {
    for j in 1...str2.count {
        if str1[i-1] == str2[j-1] {
            LCS1[i][j] = LCS1[i-1][j-1] + 1
        }
        else {
            LCS1[i][j] = max(LCS1[i][j-1],LCS1[i-1][j])
        }
    }
}
var i = str1.count
var j = str2.count
let maxValue = LCS1.flatMap{$0}.max() ?? 0
while true {
    if LCS_str.count >= maxValue {
        break
    }
    if LCS1[i][j] == LCS1[i][j-1] {
        j = j-1
    }
    else if LCS1[i][j] == LCS1[i-1][j] {
        i = i-1
    }
    else {
        i = i-1
        j = j-1
        LCS_str += str1[i]
    }
}
let str4 = String(LCS_str.reversed()).map { String($0) }
if str4.count < 1 {
    print("0")
}
else {
    var LCS2 = Array(repeating: Array(repeating: 0, count: str3.count+1), count: str4.count+1)
    for i in 1...str4.count {
        for j in 1...str3.count {
            if str4[i-1] == str3[j-1] {
                LCS2[i][j] = LCS2[i-1][j-1] + 1
            }
            else {
                LCS2[i][j] = max(LCS2[i][j-1],LCS2[i-1][j])
            }
        }
    }
    print(LCS2.flatMap{$0}.max()!)
}

✍️ 두번째 접근

다음과 같이 문자열이 들어올 경우가 반례이다. 따라서, 첫번째 접근과 다르게 첫번째 문자열, 두번째 문자열, 세번째 문자열에 대한 LCS를 한번에 구해 해결할 수 있었다.

A: dababcf
B: ababdef
C: df

LCS(A,B): ababf
LCS(LCS(A,B),C):  f
LCS(A,B,C): df

import Foundation

let str1 = readLine()!.map { String($0) }
let str2 = readLine()!.map { String($0) }
let str3 = readLine()!.map { String($0) }
var LCS = Array(repeating: Array(repeating: Array(repeating: 0, count: str3.count+1), count: str2.count+1), count: str1.count+1)
for i in 1...str1.count {
    for j in 1...str2.count {
        for k in 1...str3.count {
            if str1[i-1] == str2[j-1] && str2[j-1] == str3[k-1]{
                LCS[i][j][k] = LCS[i-1][j-1][k-1] + 1
            }
            else {
                LCS[i][j][k] = max(LCS[i][j][k-1],LCS[i-1][j][k],LCS[i][j-1][k])
            }
        }
    }
}
print(LCS.flatMap{$0}.flatMap{$0}.max()!)