문제 풀이 아이디어

🚫 브루탈 포스

1에서 s.count까지 모든 길이의 subString을 브루탈 포스를 통해서 확인하는 것은 불가능합니다. s의 최대 길이가 2500이기 때문입니다.

✅ DP

펠린드롬에는 규칙이 있다!

펠린드롬에는 규칙이 있기 때문에 규칙이 없는 경우에 사용하는 브루탈 포스를 사용할 필요가 없습니다. 길이가 3인 펠린드롬을 구하기 위해서는 길이가 1인 펠린드롬의 양 끝에 같은 문자를 붙이면 됩니다. 마찬가지로 길이가 4인 펠린드롬을 구하기 위해서는 길이가 2인 펠린드롬의 양 끝에 같은 문자를 붙이면 됩니다.

반대로 이야기하면 길이가 n인 문자열의 첫 번째와 마지막 문자가 동일한데, 2번째 ~ (n -1) 번째가 펠린드롬이라면 그 문자열을 펠린드롬이라고 볼 수 있습니다.

초기값

위에서 찾은 규칙은 양 끝에 같은 문자열을 확인해서 펠린드롬을 구하므로 길이가 3이상인 펠린드롬부터 구할 수 있습니다. 따라서 길이가 1 혹은 2인 펠린드롬은 초기값으로 입력해야 합니다.

모든 길이가 1인 문자열을 펠린드롬입니다. 같은 문자로 구성된 길이가 2인 문자열은 펠린드롬입니다.

// f(x, y): 문자열의 x번째 문자 ~ y번째 문자로 구성된 문자열이 펠린드롬인지 여부

// 길이가 1인 펠린드롬
f(x, x) = true

// 길이가 2인 펠린드롬 
if s[x] == s[x + 1] : f(x, x + 1) = true

점화식

위에서 찾은 규칙을 점화식으로 표현하면 아래와 같습니다.

// 길이가 l인 펠린드롬
if s[x] == s[x + l - 1] && f(x + 1, y + l - 2):	f(x, x + l - 1) = true

코드

스위프트의 문자열을 index로 접근하거나 subString을 만드는 작업은 cost가 높은 동작입니다. Array로 바꾸어서 구현하도록 합시다.

func solution(_ s:String) -> Int {

    let s = s.map { $0 }
    var dp = Array(repeating: Array(repeating: false, count: s.count), count: s.count)
    var ans = 1
    

    // 초기 값: 길이가 1 혹은 2인 펠린드롬
    for i in 0..<s.count {
        dp[i][i] = true
        if i + 1 < s.count && s[i] == s[i + 1] {
            dp[i][i + 1] = true
            ans = 2
        }
    }
    
    // 길이 3인 펠린드롬 부터 구하기
    var length = 3

    // 각각의 길이별로 펠린드롬 점화식으로 펠린드롬 여부 확인
    while length <= s.count {
        var i = 0
        while i + length - 1 < s.count {
            if dp[i + 1][i + length - 2] == true && s[i] == s[i + length - 1] {
                dp[i][i + length - 1] = true
                ans = length
            }
            i += 1
        }
        length += 1
    }

    return ans
}