[프로그래머스] 가장 긴 팰린드롬 with Kotlin

문제

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

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

 

제한사항

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

 

풀이 과정

1. for문으로 2500부터 내려오면서 i의 길이만큼 문자열 s를 잘라서 탐색
   1. 탐색 방법 >> 문자열 중간부터 양쪽으로 문자가 같은지 다른지 확인
2. 팰린드롬이 있다면 반복문 종료 이후 i 반환
3. 문자열을 잘라서 확인하는 방법
   1. substring >> 편하긴 하지만 효율성 1번에서 시간초과 나옴
   2. 시작 인덱스와 확인 할 문자열의 길이의 중간 값을 활용하여 확인

개인적인 풀이방법 입니다.

 

코드

class Solution {
    fun solution(s: String): Int {
        var answer = 0
 
        for(i in s.length downTo 1){
            var status = true // 팰린드롬인지 아닌지
            
            var start = 0
            while(start + i <= s.length){
                //val word = s.substring(start, start + i)
                val midIndex = i/2 + start // 중간 인덱스는 길이/2 + 시작 인덱스
                
                status = true
                for(n in 1..i/2){
                    // 홀수
                    if(i % 2 == 1){
                        if(s[midIndex+n] != s[midIndex-n]){
                            status = false
                            break
                        }
                    }
                    // 짝수
                    else{
                        if(s[midIndex-n] != s[midIndex-1+n]){
                            status = false
                            break
                        }
                    }
                }
                
                // 팰린드롬을 찾았다면 종료
                if(status) break
                
                start += 1
            }
            
            // 팰린드롬을 찾았다면 종료
            if(status){
                answer = i
                break
            }
        }

        return answer
    }
}