BOJ-9251 LCS Swift

문제

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

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

입력

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

출력

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

내가 푼 풀이

- dp[i][j] = 길이 i인 문자 s1과 길이 j인 문자 s2 의 가장 긴 수열의 길이라 한다.

- s1, s2 문자열을 순회한다.

• 문자가 같으면 dp[i-1][j-1] + 1
• 문자가 다르면 max( dp[i-1][j], dp[i][j-1] )

		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
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

import Foundation

var str1 = readLine()!
var str2 = readLine()!
var strArr1 = ["0"] + str1.map{String($0)}
var strArr2 = ["0"] + str2.map{String($0)}
var dp = Array(repeating: Array(repeating: 0, count: str1.count+1), count: str2.count+1)


for i in 1...str2.count {
    for j in 1...str1.count {
        if strArr2[i] == strArr1[j] {
            dp[i][j] = dp[i-1][j-1] + 1
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        }
    }
}

print(dp[str2.count][str1.count])