[프로그래머스] 가장 긴 팰린드롬 - Swift

안녕하세요. 오늘은 가장 긴 팰린드롬 문제에 대해서 기록해 보려고 해요.

난이도는 level 3입니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스

 

처음에 문제를 잘못 이해하기도 했고...

반례를 아예 생각하지 못한 코드를 작성하기도 했고...

이것저것 찾아보면서 고민해 보다가 2시간 만에 겨우 풀었네요 ㅠ

 

2시간 동안의 삽질과 의문들, 왜 그 코드는 틀렸었고, 수정한 코드는 맞았는지에 대해 적어두려고 해요.

 

---

먼저 저는 DP로 접근했습니다.

 

 

dp[i][j] : 문자열 s의 i번째 문자부터 j번째 문자까지의 부분 문자열이 팰린드롬인지 여부

 

이 문제를 해결하기 위해 다음과 같은 점화식을 도출할 수 있었어요.

s[i] == s[j] : dp[i][j] = dp[i+1][j-1]
s[i] != s[j] : dp[i][j] = false

이 점화식은 i번째 문자와 j번째 문자가 같은 경우, i+1번째 문자부터 j-1번째 문자까지의 부분 문자열이 팰린드롬인지의 여부를 검사하여 판단합니다.

이때, i+1번째 문자부터 j-1번째 문자까지의 부분 문자열이 팰린드롬인지의 여부는 이미 이전에 계산된 결과를 사용할 수 있기 때문에, DP를 적용할 수 있어요.

 

이 점화식을 사용하여서 문자열 s의 모든 부분 문자열에 대해 팰린드롬 여부를 검사하면, 가장 큰 팰린드롬의 길이를 찾을 수 있습니다. 이때, 가장 긴 팰린드롬의 길이는 dp[i][j] = true이고, 모든 i와 j에 대해 j-i+1의 최대값을 구하면 됩니다.

 

 

그런데... 점화식대로 적었는데 제 코드가 계속해서 17, 18 case에서 틀렸었습니다 ㅠㅠ

정답이 틀렸다고 얘기하는 것이 아닌, index error와 같은 오류가 발생했었는데요. 제 처음 코드는 이러했습니다.

 

import Foundation

func solution(_ s:String) -> Int {
    let number = s.count
    var dp = Array(repeating: Array(repeating: false, count: number+1), count: number+1)
    var result = 1
    let s = s.map{String($0)}
    
    // 길이가 1인 팰린드롬
    for i in 0..<number {
        dp[i][i] = true
    }
    
    // 길이가 2인 팰린드롬
    for i in 0..<number-1 {
        if s[i] == s[i+1] {
            dp[i][i+1] = true
            result = 2
        }
    }
    
    // 길이가 3 이상인 모든 팰린드롬
    for len in 3...number {
        for i in 0...number-len {
            let j = i + len - 1
            if s[i] == s[j] && dp[i+1][j-1] {
                dp[i][j] = true
                result = max(result, len)
            }
        }
    }
    
    // len은 검사할 부분 문자열의 길이
    // i는 부분 문자열의 시작 인덱스
    // j는 부분 문자열의 마지막 인덱스
    // i+1부터 j-1까지의 부분 문자열이 팰린드롬이어야 dp[i][j] = true가 성립함
    
    return result
}

문제가 없어 보이죠?

 

하지만 반례로 s의 길이가 1이거나 2일 때 문제가 발생합니다.

 

일단 s가 a일 경우 result가 1이 출력되어야 하지만, 길이가 2인 팰린드롬을 찾다가 index error가 발생합니다.

그래서 s.count == 1일 때 return 1을 해 주는 코드를 작성해 주어야 inder error가 발생하지 않네요.

 

또 다른 반례로는 s가 aa일 경우 또는 ab일 경우입니다.

s의 길이가 2이면서 그자체로 팰린드롬의 조건일 경우, 2로 바뀐 result를 출력해 주어야 하고,

2이지만 팰린드롬의 조건을 충족하지 못한 경우 1인 result를 출력해 주어야 합니다.

추가로 팰린드롬의 길이가 3인 for문을 돌기 전에 if문을 걸어서 result으로 함수를 끝내주어야 해요.

 

import Foundation

func solution(_ s:String) -> Int {
    // 짝수 팰린드롬이랑 홀수 팰린드롬을 나눠서 생각해야 함
    let number = s.count
    var dp = Array(repeating: Array(repeating: false, count: number+1), count: number+1)
    var result = 1
    let s = s.map{String($0)}
    
    if number == 1 { return 1 }
    
    // 길이가 1인 팰린드롬
    for i in 0..<number {
        dp[i][i] = true
    }
    
    // 길이가 2인 팰린드롬
    for i in 0..<number-1 {
        if s[i] == s[i+1] {
            dp[i][i+1] = true
            result = 2
        }
    }
    
    if s.count == 2 { return result }
    
    // 길이가 3 이상인 모든 팰린드롬
    for len in 3...number {
        for i in 0...number-len {
            let j = i + len - 1
            if s[i] == s[j] && dp[i+1][j-1] {
                dp[i][j] = true
                result = max(result, len)
            }
        }
    }
    
    // len은 검사할 부분 문자열의 길이
    // i는 부분 문자열의 시작 인덱스
    // j는 부분 문자열의 마지막 인덱스
    // i+1부터 j-1까지의 부분 문자열이 팰린드롬이어야 dp[i][j] = true가 성립함
    
    return result
}

if문을 추가하여 index error를 방지시켜 주면 올바른 정답을 도출할 수 있게 돼요. :)