[프로그래머스/자바] 가장 긴 팰린드롬 풀이

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

프로그래머스

 

프로그래머스 코딩테스트 연습 Level 3 문제다.

 

주의할 점

- StringBuilder의 reverse와 String의 substring은 피하자. (substring은 O(n))

- 팰린드롬의 길이가 무조건 홀수는 아니다. abba 처럼 짝수인 경우도 존재한다. (테케 12번)

 

 

위 사항을 간과한 채 문제를 풀었더니 4, 6, 7, 12, 효율성1 테케가 틀렸었다.

substring 대신 인덱스 하나하나 비교하기 위해 char[]를 사용했다. (String의 charAt도 사용가능)

 

먼저 기준이 될 문자에서 그 주변의 문자를 비교하면서 같은 경우 팰린드롬이므로 answer를 갱신하는 방식으로 코드를 짰다.

 

        for(int i=1;i<n-1;i++) { // i -> 기준이 될 문자의 인덱스
            odd(i); // 길이가 홀수
            even(i); // 길이가 짝수
        }

기준이 될 문자는 문자열 전체의 1 ~ (length-2)가 될 수 있으므로 위와 같이 작성한다.

odd와 even 함수는 i를 기준으로 하는 문자열의 길이가 홀수/짝수인 경우 팰린드롬을 만족하는지 검사하는 함수다.

 

    static void odd(int idx) {
        for(int i=1;i<=n/2;i++) {
            if((idx - i) >= 0 && (idx + i) < n && c[idx - i] == c[idx + i]) {
                answer = Math.max((i * 2 + 1), answer);
            }
            else break;
        }
    }

팰린드롬의 길이가 홀수인 경우는 가운데 문자를 기준으로 양 옆의 문자를 비교하면 된다.

문자열의 범위를 벗어나지 않는 경우까지 1씩 증가해가며 양 옆 문자를 비교한다.

문자열의 범위를 벗어났거나, 양 옆 문자가 다르다면 팰린드롬이 아닌 것이므로 함수를 종료한다.

양 옆 문자가 같다면 팰린드롬인 것이므로 answer를 갱신한다.

 

 

    static void even(int idx) {
        for(int i=1;i<=n/2;i++) {
            if((idx - i) >= 0 && (idx + i - 1) < n && c[idx - i] == c[idx + i - 1]) {
                answer = Math.max(i * 2, answer);
            }
            else break;
        }
    }

팰린드롬의 길이가 홀수인 경우는 기준이 되는 문자와 왼쪽 문자를 비교하면 된다.

odd 함수와 동일하게 문자열의 범위를 벗어나지 않는 경우까지 1씩 증가해가며 양 옆 문자를 비교하며 answer를 갱신한다. 

이때 가장 처음으로 비교할 때 기준이 되는 문자까지 비교해야 하므로, idx + i가 아닌 idx + i - 1이다.

 

 

 

전체 코드

class Solution {
    static int n;
    static int answer = 1;
    static char[] c;
    
    static void odd(int idx) {
        for(int i=1;i<=n/2;i++) {
            if((idx - i) >= 0 && (idx + i) < n && c[idx - i] == c[idx + i]) {
                answer = Math.max((i * 2 + 1), answer);
            }
            else break;
        }
    }
    
    static void even(int idx) {
        for(int i=1;i<=n/2;i++) {
            if((idx - i) >= 0 && (idx + i - 1) < n && c[idx - i] == c[idx + i - 1]) {
                answer = Math.max(i * 2, answer);
            }
            else break;
        }
    }
    
    public int solution(String s) {
        c = s.toCharArray();
        n = s.length();
        
        for(int i=1;i<n-1;i++) { // i -> 기준이 될 문자의 인덱스
            odd(i); // 길이가 홀수
            even(i); // 길이가 짝수
        }
        
        return answer;
    }
}