백준 1958 LCS 3

출처: www.acmicpc.net/problem/1958

분류: LCS, 문자열, DP

---

접근방식

이번엔 3개 문자열의 LCS를 구하는 문제였습니다.

기존 LCS와 원리는 동일하고 이를 3차원 배열로 확장시키면 되는 문제였습니다.

func lcs(_ strA: [Character], _ strB: [Character], strC: [Character]) -> Int {
    
    var table = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: strC.count+1), count: strB.count+1), count: strA.count+1)
    
    for a in 1...strA.count {
        for b in 1...strB.count {
            for c in 1...strC.count {
                if strA[a-1] == strB[b-1], strA[a-1] == strC[c-1] {
                    table[a][b][c] = table[a-1][b-1][c-1]+1
                } else {
                    table[a][b][c] = max(table[a-1][b][c], table[a][b-1][c], table[a][b][c-1])
                }
            }
        }
    }
    
    table[strA.count][strB.count][strC.count]
}

 

문제는 여기까지지만, 이대로 끝내긴 아쉬우니 LCS 문자열을 만드는 방법까지 살펴보고 갈게요.

역시나 원리는 똑같습니다. 3차원만 더 추가해주시면 돼요. 예전에는 backtracking 방식의 재귀호출로 구했는데 이번엔 그냥 while문으로 구하고 뒤집어서 결과를 찾아보겠습니다.

위 방식대로 table이 만들어졌다면, 이런 방식으로 문자열을 찾아줄 수 있답니다 :)

var a = strA.count
var b = strB.count
var c = strC.count

var result = ""
while table[a][b][c] > 0 {
    if table[a-1][b][c] == table[a][b-1][c], table[a-1][b][c] == table[a][b][c-1] {
        a -= 1; b -= 1; c -= 1
        result.append(strA[a])
    } else if table[a-1][b][c] > table[a][b-1][c], table[a-1][b][c] > table[a][b][c-1] {
        a -= 1
    } else if table[a][b-1][c] > table[a-1][b][c], table[a][b-1][c] > table[a][b][c-1] {
        b -= 1
    } else {
        c -= 1
    }
}
print(String(result.reversed()))

 

 

해결방법

let str1 = Array(readLine()!)
let str2 = Array(readLine()!)
let str3 = Array(readLine()!)

func lcs(_ strA: [Character], _ strB: [Character], strC: [Character]) {
    
    var table = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: strC.count+1), count: strB.count+1), count: strA.count+1)
    
    for a in 1...strA.count {
        for b in 1...strB.count {
            for c in 1...strC.count {
                if strA[a-1] == strB[b-1], strA[a-1] == strC[c-1] {
                    table[a][b][c] = table[a-1][b-1][c-1]+1
                } else {
                    table[a][b][c] = max(table[a-1][b][c], table[a][b-1][c], table[a][b][c-1])
                }
            }
        }
    }
    
    print(table[strA.count][strB.count][strC.count])
}

lcs(str1, str2, strC: str3)

 

배운점