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

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

✍️ 첫번째 접근

문제 제목에서도 알 수 있듯이, LCS(Longest Common Substring) 알고리즘을 적용하는 문제이다.
어째서인지...시간 초과가 발생하였다. Swift는 문자열에 대한 접근이 안 좋다는 기억이 되살아났다.

import Foundation

extension String {
    subscript(_ index: Int) -> Character {
        return self[self.index(self.startIndex, offsetBy: index)]
    }
}

let str1 = readLine()!
let str2 = readLine()!
let maxLength = max(str1.count,str2.count)
var LCS = Array(repeating: Array(repeating: 0, count: maxLength+1), count: maxLength+1)
for i in 0..<str1.count {
    for j in 0..<str2.count {
        if i == 0 || j == 0 {
            continue
        }
        if String(str1[i]) == String(str2[j]) {
            LCS[i][j] = LCS[i-1][j-1] + 1
        }
        else {
            LCS[i][j] = 0
        }
    }
}
print(LCS.flatMap{$0}.max() ?? 0)

✍️ 두번째 접근

첫번째 접근에서 extension을 사용해 Int형으로 원하는 위치의 문자열 요소에 접근할 수 있는 기능을 구현하였다.
문자열 각각의 인덱스를 접근하지 말고, 입력받을 때 String 타입이 아니라 Array 타입으로 저장하였다. 또한 for문 안에서 i 또는 j가 0일 때 continue를 하게 되면 각 문자열의 첫번째 글자를 무시하게 되므로 이를 삭제하여 해결하였다.

import Foundation

let str1 = readLine()!.map { String($0) }
let str2 = readLine()!.map { String($0) }
let maxLength = max(str1.count,str2.count)
var LCS = Array(repeating: Array(repeating: 0, count: maxLength+1), count: maxLength+1)
for i in 1...str1.count {
    for j in 1...str2.count {
        if str1[i-1] == str2[j-1] {
            LCS[i][j] = LCS[i-1][j-1] + 1
        }
        else {
            LCS[i][j] = 0
        }
    }
}
print(LCS.flatMap{$0}.max() ?? 0)