[프로그래머스] Swift - 가장 긴 팰린드롬 (LV.3)

👆문제풀러 가기👆

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

 

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

예상 문제 풀이 방식

1. 완탐 -> 전체 문자열에서 팰린드롬 구하기 or 팰린드롬만 찾기

2. DP

 

 

전체 문자열에서 팰린드롬을 구하면, 시간초과가 날 것 같은 느낌이 들지만, 일단 시도해보자.

func solution(_ s:String) -> Int {
    let s = s.map { String($0) }
    var array = [String]()
    
    func findString(_ num: Int) { // 부분문자열 찾기
        for i in 0..<s.count-num {
            let temp = Array(s[i...i+num])
            
            if temp == temp.reversed() { // 팰린드롬만 확인
                array.append(temp.joined())
                break // 현 배열에서 가장 긴 팰린드롬을 찾음.
            }
        }
    }

    for i in 0..<s.count {
        findString(i)
    }
    
    var result = 0

    for i in stride(from: array.count-1, through: 0, by: -1) {
        let length = array[i].count 

        if result < length { // 가장 긴 팰린드롬 길이는?
            result = length
            break
        }
    }

    return result
}

 

역시나 시간초과. 아무래도 전체 문자열 길이에서부터 찾으려고 하니 정확성 테스트는 문제 없지만, 효율성 검사에서 시간초과가 발생하는 것 같다.

 

코드를 개선해보자.

 

풀이1

func solution(_ s:String) -> Int {
    var result = 0
    
    func find(_ i: Int, _ s: String) -> String {
        let s = s.map { String($0) }
        var left = i
        var right = i
        
        while (left-1 >= 0) && s[left] == s[left-1] {
            left -= 1
        }
        
        while (right+1 < s.count) && s[right] == s[right+1] {
            right += 1
        }
        
        while (left-1 >= 0) && (right+1 < s.count) && s[left-1] == s[right+1] {
            left -= 1
            right += 1
        }
        
        return s[left...right].joined()
    }
    
    for i in 0..<s.count {
        let palin = find(i, s)
        
        if result < palin.count {
            result = palin.count
        }
    }
    
    return result
}

while문으로, 현재 인덱스의 문자를 기준으로 좌우로 확장해가며 팰린드롬을 찾아냈다.

중간에 팰린드롬이 아닌 문자열이 발견되면 종료되므로, 함수에서 빠르게 탈출할 수 있다.

효율성 테스트에서 500~1000ms 사이의 값이 나오는 게 조금 마음에 안 든다.

dp로도 가능해보이는데, dp로 풀어보자.

 

풀이2

func solution(_ s:String) -> Int {
    var length = s.count
    
    if length == 1 { return 1 }
    
    let s = s.map { String($0) }
    var dp = Array(repeating: Array(repeating: false, count: length), count: length)
    var left = 0
    var right = 0
    
    for i in 1..<length {
        // 첫글자(s[i])와 끝글자(s[j])가 같은 글자이며
        // 이전에 팰린드롬임이 확인 된 글자이면 이번 글자도 팰린드롬이다.
        // 만약 양끝값(s[i]와 s[j])는 같은데, 내부 글자가 팰린드롬이 아니었으면, 확인할 필요 없으므로 (i-j <= 2)범위만 확인한다.
        for j in 0..<i where s[i] == s[j] && (dp[j+1][i-1] || i-j <= 2) {
            dp[j][i] = true
            
            if i-j > right-left {
                left = j
                right = i
            }
        }
    }
    let result = s[left...right].joined()
    
    return result.count
}

역시 dp가 최고인가..?

효율성 테스트에서 100~130ms 정도로 개선되었다.

이전 풀이 500~1000ms에 비해 5~10배 정도 개선된 것.

하지만 풀이 시간은 배 이상이 들었기 때문에, 좀 더 연습이 필요해보인다.