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

• 문제

풀이과정

• 팰린드롬은 크게 두 가지 종류로 구분할 수 있다.

  1. 글자 하나를 중심으로 서로 대칭을 이루는 팰린드롬 (팰린드롬의 길이가 홀수)
     • a, aba, aaa, abbb 등
  2. 글자 두 개를 중심으로 서로 대칭을 이루는 팰린드롬 (팰린드롬의 길이가 짝수)
     • aa, abba, aaaa, abcc 등

• 풀이의 진행과정은 다음과 같다.

  1. 특정 index i 번 째 문자 하나를 중심으로 팰린드롬을 이룬다고 가정하고 최대 팰린드롬의 길이를 구한다.
  2. 특정 index i 및 i + 1 번 째 문자 두 개를 중심으로 팰린드롬을 이룬다고 가정하고 최대 팰린드롬의 길이를 구한다. (해당 문자 두 개가 서로 다를 경우 최대 팰린드롬의 길이는 1이다.)
  3. 1과 2에서 구한 값들 및 기존에 구한 최대 팰린드롬의 길이 중 가장 긴 값을 선택한다.
  4. index i를 1에서부터 문자열 길이 - 1까지 변화시켜가며 루프를 돈 후 최종 결과를 반환한다.
     • 4번의 조건에 의해 주어진 문자열의 길이가 0 또는 1일 경우 반복문에 들어가지 않는다.
     • 이 때, 빈 문자열이라면 최대 팰린드롬의 길이는 당연히 0이고, 길이가 1인 문자열이여도 최대 팰린드롬의 길이는 당연히 1이므로 주어진 문자열의 길이를 바로 반환할 수 있도록 한다.

Code

class Solution {
    public int solution(String s) {
        char[] chars = s.toCharArray();
        int answer = chars.length < 2 ? chars.length : 1;
        for (int i = 1; i < chars.length - 1; i++) {
            // 1. palindrome 의 길이를 홀수로 가정 e.g. "a", "aba", "aaa", "abbb" ...
            int oddLength = calcPalindrome(chars, i, i);
            // 2. palindrome 의 길이를 짝수로 가정 e.g. "aa", "abba", "kkkk", "abkk" ...
            int evenLength = calcPalindrome(chars, i, i + 1);

            answer = Math.max(answer, Math.max(oddLength, evenLength));
        }

        return answer;
    }

    private int calcPalindrome(char[] chars, int leftCharIdx, int rightCharIdx) {
        if (chars[leftCharIdx] != chars[rightCharIdx]) {
            return 1;
        }

        int answer = 1 + (rightCharIdx - leftCharIdx);
        for (int i = 1; (leftCharIdx - i >= 0) && (rightCharIdx + i < chars.length); i++) {
            if (chars[leftCharIdx - i] == chars[rightCharIdx + i]) {
                answer += 2;
            } else {
                break;
            }
        }
        return answer;
    }
}

결과