[Leetcode/Medium] 가장 긴 팰린드롬 부분 문자열 (5. Longest Palindrome Substring, Swift)

https://leetcode.com/problems/longest-palindromic-substring/description/

 

🤔 문제 설명

가장 긴 팰린드롬(Palindrome) 부분 문자열을 출력하세요.

팰린드롬에 대한 설명은 2024.06.27 - [Algorithm] - [Leetcode/Easy] 유효한 팰린드롬 (125. Valid Palindrome, Swift) 글 참조

s = "babad"
// "bab"

 

💡 처음 생각한 풀이와 코드 (Swift ver.)

가장 긴 부분의 팰린드롬을 찾는 문제이기 때문에 문장 전체부터 시작해 길이를 하나씩 줄여가면서 팰린드롬을 확인하는 방식을 생각했다.

문제의 예시로 나와있는 "babad"로 설명을 들어보자면,
문장의 길이(=5) 기준으로 처음에는 인덱스 0~4 부분이 팰린드롬인지 확인 -> 맞으면 바로 return 아니면, 다음 반복 (뒤 인덱스가 문장의 마지막 인덱스보다 같을 경우까지) 수행
문장 길이를 -1한 후, 0~3 부분 확인 -> 1~4 부분 확인... 이런 식으로 계속 반복을 하면서 팰린드롬을 확인하는 방법이었다.

이때 사용한 Swift 언어에서 String 타입을 슬라이싱 하기 위해 사용한 문법 몇 개를 같이 정리해 보자.

• String.Index 타입을 사용하면, Python처럼 string[String.Index] 방식으로 String을 슬라이싱할 수 있게 된다. -> Int 타입과는 구분된다.
• string.startIndex로 문자열의 첫 번째 인덱스를 가져올 수 있고, string.endIndex로 문자열의 마지막 인덱스를 가져올 수 있다. 
• string[startIndex...lastIndex]로 원하는 문자열을 뽑을 수도 있다. 이때 반환되는 타입은 String과 구분되는 SubString 타입!
• string.index(before:)로는 String.Index 값을 한 칸 앞으로, string.index(after:)로는 String.Index 값을 한 칸 뒤로, string.index(_: offsetBy:)로는 원하는 offset만큼 뒤의 String.Index 값을 가져올 수 있게 된다.

class Solution {
    func longestPalindrome(_ s: String) -> String {
        var longestCount = s.count

        while (longestCount >= 1) {
            var startIndex: String.Index = s.startIndex
            var lastIndex: String.Index = s.index(startIndex, offsetBy: longestCount-1)

            while (lastIndex < s.endIndex) {
                var checkString = s[startIndex...lastIndex]
                if (checkString == String(checkString.reversed())) {
                    return String(checkString)
                }
                startIndex = s.index(after: startIndex)
                lastIndex = s.index(after: lastIndex)
            }
            longestCount -= 1
        }

        return ""
    }
}

하지만, 해당 코드는 46번째 test case에 대해 Time Limit Exceeded 에러가 발생하며 통과하지 못했다.

다른 방식으로 다시 도전해 보겠다.

 

💡 개선한 풀이 - Two Pointers

<파이썬 알고리즘 인터뷰> 책에서는 "투 포인터"라는 방법을 이용한 풀이를 제안하고 있었다.

복잡하지 않고 그저 양 끝 문자열의 인덱스를 갖고 있다가, 이상이 없는 경우 양 끝을 점차 늘려가는 식으로 반복하는 형태의 풀이 방법이었다.
여기서 말하는 이상이 없는 경우는 총 세 가지 조건이 있을 수 있겠다.

1. 왼쪽 포인터가 0 이상일 때 -> 문자열의 첫 번째를 left가 가리키면 더 이상 확장할 수 없기 때문
2. 오른쪽 포인터가 문자열의 길이 미만일 때 -> 문자열의 마지막을 right가 가리키면 마찬가지로 더 이상 확장할 수 없기 때문
3. 왼쪽 문자와 오른쪽 문자가 같을 때 = 팰린드롬을 확인하는 조건에 해당한다. (최소 길이부터 판단하기 때문에 양끝만 계속 같은지 판단해 주면, 팰린드롬을 판단하는 것과 마찬가지인 셈이다.)

이제는 문자열을 처음부터 반복하면서 판단을 해주면 되는데,
이때 주의할 점 하나는 길이가 홀수일 때의 팰린드롬과, 짝수일 때의 팰린드롬을 모두 각각 비교해줘야 한다는 것이다.

expand(i, i+1)로 시작하는 짝수 길이의 문자열 (최소 길이 2부터 4, 6... 순서대로 판단)
expand(i, i+2)로 시작하는 홀수 길이의 문자열 (최소 길이 3부터 5, 7... 순서대로 판단)
*길이가 0 또는 1인 경우에는 가장 처음에 예외 처리를 두었다. = 팰린드롬을 판별할 필요 없이 무조건 팰린드롬 문자열이기 때문!

 

🧑🏻‍💻 코드 (Swift ver.)

Runtime : 20ms (Beats 66.55%), Memory : 16.56MB (Beats 46.27%)

class Solution {
    func longestPalindrome(_ s: String) -> String {
        let n = s.count
        let sArray = Array(s)

        // 예외 처리: 문자열의 길이가 0, 1인 경우는 그냥 그 자체가 팰린드롬 
        if n < 2 { return s } 

        // 최적의 팰린드롬일 때 인덱스를 저장하는 변수
        var startIndex = 0
        var endIndex = 0

        // 중심 확장하는 함수
        func expand(_ left: Int, _ right: Int) -> (Int, Int) {
            var l = left
            var r = right
            
            while (l>=0 && r<n && sArray[l]==sArray[r]) {
                l -= 1
                r += 1
            }            
            return (l+1, r-1)
        }

        // 문자열 반복하면서 expand 메서드로 팰린드롬 확인 -> 누적 팰린드롬 인덱스 길이와 최종 비교
        for i in 0..<n {
            let (evenLeft, evenRight) = expand(i, i+1)  // 짝수 길이 팰린드롬
            let (oddLeft, oddRight) = expand(i, i+2)    // 홀수 길이 팰린드롬
            
            if (evenRight-evenLeft > oddRight-oddLeft) {
                startIndex = (evenRight-evenLeft > endIndex-startIndex) ? evenLeft : startIndex
                endIndex = (evenRight-evenLeft > endIndex-startIndex) ? evenRight : endIndex
            } else {
                startIndex = (oddRight-oddLeft > endIndex-startIndex) ? oddLeft : startIndex
                endIndex = (oddRight-oddLeft > endIndex-startIndex) ? oddRight : endIndex
            }
        }

        return String(sArray[startIndex...endIndex])
    }
}