백준 9252 LCS 2

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

분류: LCS

---

접근방식

최장 증가 수열을 찾는 전통적인 LCS 문제입니다.

문자열을 그대로 사용하면 시간초과가 나서 길이 테이블을 완성하고 백트래킹을 통해 문자열을 찾아주는 방식으로 해결했습니다.

 

LCS는 다음과 같이 두 문자열로 이차원 행렬을 완성시켜 나가는 방식으로 찾아줄 수 있습니다.

현재 칸의 두 문자열의 문자가 같다면 왼쪽 대각선 위의 문자열에 현재 문자를 붙여나갑니다. 

출처: 위키백과 https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

다르다면 위나 왼쪽 중에서 더 큰 문자열을 가져옵니다. 같다면 모두 가능한 문자열이겠죠?

 

이 원리를 이용해 저희 예제로 만들어보면

가로 CAPCAK

세로 ACAYKP

로 두면 다음과 같은 LCS 테이블을 만들 수 있습니다.

 

이제 마지막으로 마지막부터 백트래킹으로 문자열을 만들어봐야겠네요.

했던 과정을 거꾸로 돌아간다고 생각하면 됩니다.

해당 칸의 문자가 같다면 역시 왼쪽 위 대각선으로 돌아가면서 해당 칸의 문자를 붙여서 리턴,

아니라면 더 큰쪽으로 이동하고 다시 탐색해나가면 됩니다.

func backtrackLcs(r: Int, c: Int) -> String {
    if lcsTable[r][c] == 0 {
        return ""
    } else if rowStr[r-1] == colStr[c-1] {
        return backtrackLcs(r: r-1, c: c-1) + String(rowStr[r-1])
    } else if lcsTable[r-1][c] > lcsTable[r][c-1] {
        return backtrackLcs(r: r-1, c: c)
    } else {
        return backtrackLcs(r: r, c: c-1)
    }
}

 

해결방법

let rowStr = Array(readLine()!)
let colStr = Array(readLine()!)

var lcsTable = [[Int]](repeating: [Int](repeating: 0, count: colStr.count+1), count: rowStr.count+1)


for r in 1..<rowStr.count+1 {
    for c in 1..<colStr.count+1 {
        if colStr[c-1] == rowStr[r-1] {
            lcsTable[r][c] = lcsTable[r-1][c-1]+1
        } else {
            lcsTable[r][c] = max(lcsTable[r][c-1], lcsTable[r-1][c])
        }
    }
}

func backtrackLcs(r: Int, c: Int) -> String {
    if lcsTable[r][c] == 0 {
        return ""
    } else if rowStr[r-1] == colStr[c-1] {
        return backtrackLcs(r: r-1, c: c-1) + String(rowStr[r-1])
    } else if lcsTable[r-1][c] > lcsTable[r][c-1] {
        return backtrackLcs(r: r-1, c: c)
    } else {
        return backtrackLcs(r: r, c: c-1)
    }
}

print(lcsTable[rowStr.count][colStr.count])
if lcsTable[rowStr.count][colStr.count] != 0 {
    print(backtrackLcs(r: rowStr.count, c: colStr.count))
}

 

배운점