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

문제 링크

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

코딩테스트 연습 - 가장 긴 팰린드롬

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 각 인덱스에서 2가지 경우에 대해 팰린드롬 체크
   1. 자신이 바로 이전 알파벳과 동일한 경우로, 팰린드롬이 짝수 개인 경우 (...@@...)
   2. 자신이 2개 뒤에 알파벳과 동일한 경우로, 팰린드롬이 홀수 개인 경우 (...@#@...)
2. 이후 최대 길이 팰린드롬 값 반환

 문제에 대한 고민과 달리 쉽게 해결이 된 문제이다. 처음 문제를 보았을 때는 완전 탐색을 제외하고는 방법을 찾지 못해 복잡도를 줄일 수 있는 방법을 고민했으나, 단순히 새로운 방식을 찾기 보다는 탐색의 방법을 바꾸면 되는 문제였다.

 대개 이런 탐색의 경우 특정 구간의 시작 또는 끝에서 탐색을 진행하는데, 이런 경우에는 최대 길이를 찾아야 하다보니 반대편 끝까지 탐색을 마쳐야 하는 경우가 생긴다. 하지만 탐색의 시작 위치를 팰린드롬의 시작이나 끝이 아닌 중간으로 시작하면, 순차적으로 인덱스를 두 방향으로 동일하게 증가/감소 시켜나가며 값을 비교하면 그만이고 또한 강제로 탐색을 끝까지 이어나갈 필요도 없어진다.

 이에 각 위치(시작 인덱스 1)에서 반복문을 통해 진행하며, 팰린드롬이 짝수/홀수인 경우 가운데에서 대칭 모양이 달라지기 때문에 한 개 뒤에 알파벳과 두 개 뒤에 알파벳이 동일한 경우에 대해 따로 탐색을 진행하여 팰린드롬의 최대 길이를 반환하면 된다.

 

class Solution {
    public int solution(String s) {
        int answer = 1;

        if (s.length() <= 1)
            return 1;

        for (int i = 1; i < s.length(); i++) { //각 지점에서 확인
            if (s.charAt(i) == s.charAt(i - 1)) { // 팰린드롬이 짝수개인 경우 (...@@...)
                answer = Math.max(answer, countPalindrome(s, i - 1, i));
            }

            if (i > 1 && s.charAt(i) == s.charAt(i - 2)) { //팰린드롬이 홀수 개인 경우 (...@#@...)
                answer = Math.max(answer, countPalindrome(s, i - 2, i));
            }
        }

        return answer;
    }

    int countPalindrome(String s, int index1, int index2) {//팰린드롬 길이 확인
        while (index1 >= 0 && index2 < s.length() && s.charAt(index1) == s.charAt(index2)) {
            --index1;
            ++index2;
        }

        return index2 - index1 - 1;
    }
}

결과