[Swift] 5582 공통 부분 문자열 (DP)

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

 

생각

처음엔 contains 함수를 사용하여 일일이 길이를 구했는데 시간초과가 났다.

시간을 줄이기 위해서 DP를 사용

 

풀이

만약 [i]와 [j]의 알파벳이 같다면 [i-1][j-1] 까지의 공통 부분 길이에서 1을 더해주고 저장한다.

같지 않다면 0이다.

	A	B	R
R	0	0	1
A	1	0	0
B	0	2	0

 

전체코드

import Foundation

let str1 = Array(readLine()!)
let str2 = Array(readLine()!)
var longest = 0

var dp = Array(repeating: Array(repeating: 0, count: str2.count + 1), count: str1.count + 1)

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

print(longest)