가장 긴 팰린드롬 - Kotlin

프로그래머스

문제 설명

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

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

제한사항

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

 

 나의 풀이

이 문제에서 주어진 문자열의 길이가 2500으로 비교적 짧은 길이이기 때문에 특별한 알고리즘을 사용하지 않고 진행해 보았다. 1부터 문자열의 최대 길이까지 해당하는 숫자를 중간으로 잡고 팰린드롬의 길이를 구하였다.

다만 이 방식을 사용하니 한가지 문제가 발생하였다. 만약 baac 처럼 문자가 존재한다면 한 문자를 기준으로 팰린드롬을 구했을 때 2의 결과값은 얻을 수가 없었다. 그래서 이를 고려해주기 위해 aa를 하나로 묶고 bac 이런식으로 고려해 팰린드롬을 구하는 식으로 문제를 해결할 수 있었다.

 

import kotlin.math.*

class Solution {
    var cnt = 1
    
    fun solution(s: String): Int {
        var answer = 1
                
        for (i in 1 until s.length - 1) {
            cnt = 1
            answer = max(answer, palindrome(s, i - 1, i + 1))
            
            if (s[i] != s[i + 1]) continue
            cnt = 2
            answer = max(answer, palindrome(s, i - 1, i + 2))
        }

        return answer
    }
    
    fun palindrome(s: String, left: Int, right: Int): Int {
        var leftIndex = left
        var rightIndex = right
        
        while (leftIndex >= 0 && rightIndex <= s.lastIndex) {
            if(s[leftIndex--] == s[rightIndex++])
                cnt += 2
            else break
        }
        
        return cnt
    }
}