Longest Palindromic Substring - LeetCode

문제 풀이 아이디어

Palindrome의 속성과 투 포인터

투 포인터 연속된 데이터를 다룰 때 시작점과 끝점 2개의 포인터를 가지고 다루는 기법이다. Palindrome (이하 펠린드럼)의 성격을 알면 투 포인터를 이용해서 직관적으로 풀 수 있다.

예를 들어 하나의 펠린드럼 “abba”가 있다고 치자. 이것보다 더 긴 펠린드럼을 만들기 위해서는 앞뒤에 같은 문자를 붙여주면 된다. 예를 들면 “xabbax”와 같이 말이다.

다르게 말하면 주어진 문자열 s에서 펠린드럼을 찾기 위해서는 일단 가장 작은 펠린드럼을 찾는다. 그리고 나서 해당 펠린드럼의 시작점과 끝점을 각각 왼쪽(-1), 오른쪽(+1)씩 이동하면서 왼쪽, 오른쪽 포인터가 가르키는 문자가 동일한지 확인하면 된다.

홀수 길이 Palindrome, 짝수 길이 Palindrome

투포인터 방식은 가장 작은 길이의 펠린드럼에서 시작한다. 그렇다면 가장 작은 길이의 펠린드럼은 무엇일까? 바로 길이가 1인 모든 문자열이다. 예를 들어 “a”는 거꾸로도 “a”이다. 따라서 길이가 1인 부분문자열, 다시 말하면 각각의 한글자씩 부터 시작해서 그 글자를 기준으로 왼쪽과 오른쪽에 있는 문자가 같은 문자라면 길이가 3이고 펠린드럼인 부분문자열을 찾을 수 있다.

하지만 길이가 1인 펠린드럼에서만 시작해서는 안된다. 길이가 1인 펠린드럼에서만 시작한다면 길이가 홀수인 펠린드럼만 찾을 수 있게 된다. 즉 “aa”, “baab” 같은 펠린드럼은 찾을 수 없다. 따라서 길이가 2인 펠린드럼에서도 시작해야 한다. 주어진 문자열을 2개씩 끊어서 보면서 두 부분문자열의 문자들이 동일한 경우도 확인 하도록 하자.

Swift에는 문자열에 다루는 것을 최소하자.

Python으로 문자열을 다루는 문제를 풀어본 사람들은 아마 이 문제를 풀 때 주어진 s에 직접 index로 접근하거나 count 속성을 구하거나 할 것이다.

하지만 Swift에서 문자열을 조작하는 것은 비용이 상당하다. 예를 들어 String.count는 시간복잡도가 O(n)이다. 필자는 이것을 반복문 안에서 사용했다가 실행속도가 2000ms가 나왔다. (잡아내는데 한참 걸렸다.) String.index를 계속 사용하는 것도 위험하다. 따라서 일단 String을 [Character]로 형변환을 한 후에 사용한다.

그리고 답을 저장할 때도 String을 저장하기 보다는 포인터 2개만 저장해두었다가 최종적으로 답을 리턴할 때만 String으로 변환해서 리턴하는 것이 좋다. 이때는 단 한번만 실행 되므로 무거운 작업을 해도 좋다. 반복문 안에서 사용할 때만 주의하도록 하자!

코드

class Solution {
    func longestPalindrome(_ s: String) -> String {
        
        // [Character]로 형변환
        let sArray = Array(s)
        
        // 팰린드럼을 찾는 함수
        func findPalindrome(start: Int, end: Int) -> (Int, Int) {
            // 시작 포인터와 끝 포인터
            var start = start
            var end = end
            // 시작 포인터와 끝 포인터가 같으면 각각 -1, +1 해서 추가 탐색
            while start >= 0
                    && end < sArray.count
                    && sArray[start] == sArray[end]
            {
                start -= 1
                end += 1
            }
            
            // while문이 sArray[start] != sArray[end]일 때 종료되므로 한단계 되돌린다.
            return (start + 1, end - 1)
        }

        // 중간결과는 포인터들만 저장한다.
        var longestIndices = (0, 0)
        
        // 길이가 1인 펠린드럼에서 시작해서 펠린드럼을 찾는 경우
        for i in 0..<sArray.count {
            let palindrome = findPalindrome(start: i, end: i)
            // 기존 길이보다 긴 경우에만 갱신
            if palindrome.1 - palindrome.0 > longestIndices.1 - longestIndices.0 {
                longestIndices = palindrome
            }
        }
        
        // 길이가 2인 펠린드럼에서 시작해서 펠린드럼을 찾는 경우
        for i in 0..<(sArray.count - 1) {
            // 길이가 2인 부분문자열이 펠린드럼이 아니면 continue
            guard sArray[i] == sArray[i + 1] else { continue }
            let palindrome = findPalindrome(start: i, end: i + 1)
            if palindrome.1 - palindrome.0 > longestIndices.1 - longestIndices.0 {
                longestIndices = palindrome
            }
        }
        
        // String으로 변환해서 리턴
        // [Character]의 SubSequence로 String 만들기
        return String(sArray[longestIndices.0...longestIndices.1])
    }
    
}