가장 긴 팰린드롬 (Java)

접근 방법

1. 입력 제한을 보면 입력 스트링의 길이가 2500이기 때문에, N ** 2 만큼의 효율성을 가진 알고리즘을 사용하면 되는 것을 유추할 수 있다.
2. 팰린드롬은 연속되는 문자열 중에서 중간 문자를 기준으로, 양옆으로 동일한 문자가 있는 특수한 형태의 문자열을 뜻한다.
3. 문자열의 각 문자를 기준 문자로 두고 순회하는데, 해당 문자를 기준으로 양옆으로 동일한 만큼 이동했을 때 더 이상 동일한 문자가 나오지 않을 때까지 이동한 후, 오른쪽 포인터 값에서 왼쪽 포인터 값을 빼면, 해당 기준 문자의 가장 긴 팰린드롬 길이다.
4. 기준 문자가 한 쌍으로 나올 수도 있기 때문에 순회 기준을 우선 1로 두고, i와 i-1 위치의 문자가 같으면 기준 문자가 i인 경우와 (i, i-1) 쌍이 기준 문자가 되는 경우를 둘 다 고려하며 이는 함수 오버로딩으로 구현한다.

코드

class Solution {
    private static String string;

    private static int answer;

    public void central(int i, int j) {
        int length = i == j ? 1 : 2;

        int left = i - 1;
        int right = j + 1;

        while (left >= 0 && right <= string.length() - 1) {
            if (string.charAt(left) != string.charAt(right)) break;
            left--;
            right++;
            length += 2;
        }

        if (length > answer) answer = length;
    }

    public void central(int i) {
        central(i, i);
    }

    public int solution(String s) {
        string = s;
        answer = 1;
        for (int i = 1; i < string.length(); i++) {
            if (string.charAt(i) == string.charAt(i-1)) {
                System.out.println((i-1) + " " + i);
                central(i-1, i);
            }
            central(i);
        }
        return answer;
    }
}

복기

• 문제 풀이에 착수하기 전에 꼭!! 문제 내용을 정확하게 이해하고 풀자...