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

문제 : 

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

5582번: 공통 부분 문자열

 

1. 문제 이해하기

• 두 문자열이 주어집니다.
• 문자열의 길이는 1 이상 4000 이하

 

2. 문제 풀이 생각하기

1. LCS(최장 공통 부분 수열)에 대한 문제를 풀어본 적이 있어서 문제 풀이에 대해서 어려움은 없었습니다.
2. 만약 문자열에서 나올 수 있는 모든 substring을 만들고 비교하는 방식으로 문제를 접근한다면, 최악의 경우 길이 4000짜리 문자열 하나의 substring을 뽑는 것만 4000!이라는 큰 시간이 소요될 수 있습니다.
3. LCS는 풀이 방식은 예시로 설명하겠습니다.

 

간단한 예시로 설명하겠습니다.

입력으로 ABCABC, BCAA 두 문자열이 주어졌다고 가정하겠습니다.

먼저 전체 그래프의 크기를 각각의 문자열 크기 + 1 크기로 만듭니다.

그리고 같은 문자가 나오면 왼쪽 위 대각선 값 + 1을 현재 위치에 저장합니다.

이렇게 해서 가장 큰 값을 ans에 저장합니다.

이렇게 풀이하면 O(n * m)의 시간 복잡도로 문제를 해결할 수 있습니다.

 

3. 차근차근 구현하기

import Foundation

let str1 = readLine()!.map{ String($0) }
let str2 = readLine()!.map{ String($0) }
var dp = Array(repeating: Array(repeating: 0, count: str1.count + 1), count: str2.count + 1)
var ans = 0

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

 

4. 피드백

• 화이팅하자잇!