[백준/Swift] 9252: LCS2 | PS일지

문제

9252번: LCS 2

간단한 문제 요약

LCS(Longest Common Subsequence). 최장 공통 부분 수열은 두 문자열 간 가장 긴 공통된 문자열을 찾는 것이다.

문제 풀이

 

문자열1: ABTD

문자열2: ABCD 

두 문자열이 있다면 LCSubsequence는 ABD입니다. 하지만 LCSubstring의 경우 AB(연속적인 부분 문자열)입니다. Longest Common Substring의 경우 (관련 문제 포스트가 있습니다.)

 

두 문자열 간 공통적으로 가장 긴 부분 수열을 찾기 위한 방법으로 한 문자열의 특정 prefix에 해당하는 문자 기준으로 다른 문자열의 첫 번째 부터 비교해 나가는 방법이 있습니다.

 

ABTD 문자열1을 기준으로 prefix = A일 때

문자열2 A, B, T, D 순차적 비교. 공통 부분 문자 1 일치.

 

ABTD 문자열1에서 prefix == AB일 때 문자열2에 대해서 공통된 부분 문자열 A B T D 순차적으로 비교.

이때 문자열1의 AB

문자열2의AB 비교 과정에서 이전에 구했던 경우를 반복적으로 구하게 됩니다. 사전에 문자열1의 prefix A, 문자열2의 prefix A 일때 경우를 이미 구한적 있음으로 메모제이션을 통해 저장해 나가면 효율적으로 부분 문자열을 비교할 수 있습니다.

let s1 = readLine()!.map{String($0)}
let s2 = readLine()!.map{String($0)}
var cache = Array(repeating: Array(repeating: 0, count: s2.count+1), count: s1.count+1)

두 부분 문자열을 각각 s1, s2에 받았을 때, 그리고 이전에 구했던 부분 수열길이 정보를 기록할 cahce.

for i in 1...s1.count {
    for j in 1...s2.count {
        if s1[i-1] == s2[j-1] {
            cache[i][j] = cache[i-1][j-1]+1
        }else {
            cache[i][j] = max(cache[i][j-1],cache[i-1][j])
        }
    }
}

LCS 알고리즘으로 효율적인 LCS를 구할 수 있습니다. 겉 포문은 s1의 문자 하나 하나 순차적으로 비교, 안 포문은 s1의 특정 문자일 때(cache에는 해당 문자열 이전의 문자열들 중에 최장 부분 증가 길이 기록이 저장되어 있습니다.) cache의 정보를 이용해 s1, s2 두 문자열이 일치하는지 또는 일치하지 않다면 부분 문자열의 최장 길이 정보를 어느것으로 할 지 크기 비교를 통해 cahce에 업데이트합니다.

 

cache에 업데이트하는 경우는 현재 탐색할 s1, s2의 특정 문자 s1[i-1], s2[j-1]가 같을 경우와 다른 경우 두 가지로 나뉘어있습니다. 같을 경우엔 각각의 특정 비교 문자 이전 문자까지 LCS값에 1을 더합니다. 그게 아닐 경우 s1의 특정 문자 이전 문자까지 LCS길이 or s2의 특정 문자 이전 문자까지 LCS길이 중 큰 값을 비교해서 LCS값을 cache[i][j]에 업데이트합니다. 이 문제에선 역추적을 통해 LCS의 문자를 역으로 추적해야 합니다. 

 

for i in stride(from: s1.count, through: 1, by: -1) where cache[i].contains(length) && length != 0 {
    temp.append(s2[cache[i].firstIndex(of: length)!-1])
    length -= 1
}

처음엔 단순하게 cache[i][j] max 값을 length로 지정하고 cache[i]의 처음 위치에 찾고 그 값을 기록. length -1한 값을 cahce[i]의 첫 위치 값을 문자로 계속 반환했는데 

ATCD

ABCD

이 경우

T와 B인 cahce[2][2]의 값도 1인데 이는 이전에 비교했을 때 최대값을 유지한 값이기에 로직의 오류가 있다는 것을 알게 됬습니다.

 

var x = s2.count, y = s1.count
while x>0 && y>0 {
    if cache[y-1][x] == cache[y][x] {
        y -= 1
    }else if cache[y][x-1] == cache[y][x] {
        x -= 1
    }else{
        //대각선 이전값에 부분 공통 문자열 + 1 되는 시점.
        x-=1
        y-=1
        temp.append(s2[x])
    }
}

 

 

코드

let s1 = readLine()!.map{String($0)}
let s2 = readLine()!.map{String($0)}
var cache = Array(repeating: Array(repeating: 0, count: s2.count+1), count: s1.count+1)
for i in 1...s1.count {
    for j in 1...s2.count {
        if s1[i-1] == s2[j-1] {
            cache[i][j] = cache[i-1][j-1]+1
        }else {
            cache[i][j] = max(cache[i][j-1],cache[i-1][j])
        }
    }
}
if cache[s1.count][s2.count] == 0 {
    print(0)
}else {
    var res = ""
    var temp: [String] = []
    defer{ print(res) }
    var x = s2.count, y = s1.count
    while x>0 && y>0 {
        if cache[y-1][x] == cache[y][x] {
            y -= 1
        }else if cache[y][x-1] == cache[y][x] {
            x -= 1
        }else{
            x-=1
            y-=1
            temp.append(s2[x])
        }
    }
    
    res += "\(cache[s1.count][s2.count])\n\(temp.reversed().joined(separator: ""))"
}