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

📘 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12904

💡풀이

부분 문자열 중 가장 긴 팰린드롬의 길이를 구하면 되는 문제이다.
팰린드롬이라는 것은 "aba", "bb"처럼 앞뒤가 같은 문자열을 말한다.

풀고나서 다른 사람들의 풀이를 보니 대부분 '부분 문자열'에 초점을 두고 푼 것 같지만, 나는 중심이 되는 문자에 초점을 두었다.
예를 들면 "abacd"이라는 문자열이 주어지면 각 문자를 기준으로 양옆을 비교하며 같은 지를 판단한다.

b를 기준으로 했을 때 b로부터 왼쪽으로 가는 인덱스와 오른쪽으로 가는 인덱스로 탐색하여 서로 같다면 count를 2 더해주고(왼쪽 문자와 오른쪽 문자가 추가되니까) 아니라면 그 즉시 탐색을 종료하고 다음 기준점에서부터 탐색을 진행한다.

이렇게만 하면 문제가 있다. 기준점을 하나씩 잡기 때문에 "aabbcc"같은 경우 "bb"가 기준점이 되었을 때가 가장 긴 팰린드롬 문자열이 완성이 되는데 a b(기준) b 이런식으로 탐색을 하게 되니 값이 1밖에 나오지 않는다.

이를 대비하기 위해 기준점을 두개를 잡고 위와 같이 탐색을 진행한다.
탐색 방법은 동일하지만 기준점을 잡는 것이 다르다. 아래 코드를 보면 알 수 있다.

궁금하신 점은 댓글로 남겨주세요~

💻 코드

class Solution {
    fun solution(s: String): Int {
        var answer = 1

        // start search at solo point
        for (i in 1 until s.length - 1) {
            var count = 1
            var leftGoIndex = i - 1
            var rightGoIndex = i + 1
            while (leftGoIndex >= 0 && rightGoIndex <= s.lastIndex) {
                if (s[leftGoIndex] == s[rightGoIndex]) {
                    count += 2
                } else break
                leftGoIndex--
                rightGoIndex++
            }
            answer = max(answer, count)
        }

        // start search at couple point
        for (i in 0 until s.length - 1) {
            if (s[i] != s[i + 1]) continue

            //     0 1 2 3 4 5
            // ex) a a b b c c 중 bb를 기준점이라 치면
            // leftIndex = i = 2
            // rightIndex = i+1 = 3

            val leftIndex = i
            val rightIndex = i + 1

            var count = 2

            var leftGoIndex = leftIndex - 1
            var rightGoIndex = rightIndex + 1

            while (leftGoIndex >= 0 && rightGoIndex <= s.lastIndex) {
                if (s[leftGoIndex] == s[rightGoIndex]) {
                    count += 2

                } else break
                leftGoIndex--
                rightGoIndex++
            }

            answer = max(answer, count)
        }

        return answer
    }
}

결과