BOJ-9252 LCS 2 Swift

문제

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

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

입력

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

출력

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

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

내가 푼 풀이

- 이전에 LCS를 dp를 이용하여 풀었던 기억을 떠올리며, 코드를 구현했다.

- LCS는 순서에따라 존재하는 같은 알파벳의 중 가장 긴 수열을 출력하면 된다.

- 위에 주어진 ACAYKP와 CAPCAK 에서는 순서만 고려하였을 때  ACAYKP와 CAPCAK 로 ACAK가 되는 것이다.

- 이는 이차원배열을 이용하여 순서대로 탐색했을 때, 같은 알파벳을 만난 경우, 이전 알파벳들 중 같은 알파벳을 만난 수열의 길이를 가져와 + 1을 해주면 된다.

- 다른 알파벳을 만났다면, 이전 알파벳 중 LCS가 가장 긴 수열의 길이를 넣어준다.

		A	C	A	Y	K	P
	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2

위 표대로 ACAYKP 수열에서 CAPCAK의 수열 중 알파벳 하나씩 가져와 순서대로 탐색한다.

- 첫 번째 알파벳 C를 검사했을 때, 두 번째에 있는 C와 일치하므로, ACAYKP와 C의 LCS는 C이고, 길이는 1이다.

- 이후의 알파벳은 같은 수를 만나지 않았으므로 이전의 가장 긴 수열의 길이를 가져온다.

- 두 번째 알파벳 A를 검사했을 때, 첫 번째 A와 같은 알파벳이고, 세 번째에도 A가 나온다.

- 첫번째 A는 A수열과 CA수열의 LCS이고, 세번째 A는 ACA와 CA의 LCS이다. 

- LCS: 첫 번째는 A, 세 번째는 CA가 된다.

- 동일한 알파벳을 만난다면 x-1 y-1에 위치한 lcs의 길이 +1을 해준다.

- 동일하지 않은 알파벳을 만난다면 x-1, y와 x, y-1 중 LCS길이가 더 긴 수를 가져온다.

- x-1, y-1에서 길이를 가져오는 이유는 위 표에서 x-1, y-1이 의미하는 것은 현재 검사하는 알파벳이전까지 검사했던 LCS의 최대길이 이다.

- LCS는 순서만 따졌을 때 존재하는 같은 알파벳의 수열의 최대길이가 되므로, x-1, y-1에서 가져온다.

 

길이는 다음과 같이 구하고, LCS의 수열은 역순으로 오른쪽 아래부터 x, y의 값이 x-1, y와 x, y-1의 값과 다른 경우 문자를 추가하는 방법을 사용했다.

위의 표가 만들어지는 과정의 역순으로 이용하였다.

 

코드로 구현하면 다음과 같다.

 

 

import Foundation

// 입력
var s1 = Array(readLine()!).map{ String($0) }
var s2 = Array(readLine()!).map{ String($0) }
var dp = Array(repeating: Array(repeating: 0, count: s1.count+1), count: s2.count+1)
s1.insert("0", at: 0)
s2.insert("0", at: 0)


// DP
// 같은 알파벳을 마주한경우, 이전까지 탐색했던 LCS의 최대길이 + 1을 해준다.
// 다른알파벳을 만났다면 이전에 검사했던 LCS중 가장 긴 길이를 가져온다.
for i in 1..<s2.count {
    for j in 1..<s1.count {
        if s2[i] == s1[j] {
            dp[i][j] = dp[i-1][j-1] + 1
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        }
    }
}

// LCS의 수열 구하기.
// 위의 DP표를 구했던 방법의 역순으로 구하였다.
var idx = dp[s2.count-1][s1.count-1]
var x = s1.count - 1
var y = s2.count - 1
var result = ""
while idx != 0 {
    if dp[y][x] == dp[y-1][x] {
        y -= 1
        continue
    }
    if dp[y][x] == dp[y][x-1] {
        x -= 1
        continue
    }
    result = s1[x] + result
    x -= 1
    y -= 1
    idx -= 1
}
print(result.count)
print(result)