[백준 - 21925] 짝수 팰린드롬 - Java

문제 링크

https://www.acmicpc.net/problem/21925

문제

티어: 골드 3
알고리즘: 그리디

입력

출력

짝수 팰린드롬은 최대 몇 개 있는지 출력한다.

만약 수열을 짝수 팰린드롬을 만족하도록 나눌 수 없는 경우 -1을 출력한다.

풀이

수열을 나눠서 짝수 팰린드롬을 최대한 많이 있도록 나눠야 한다.

처음 바로 드는 생각은 짝수 팰린드롬을 최대한 짧게 나누는 것이다.

N은 최대 5000이기 때문에 앞에서부터 짝수 팰린드롬이 되는 최초의 지점에서 계속 끊어가면 된다.

하지만 이러한 방식은 해결해야될 의문점이 남아있었다.

짝수 팰린드롬으로 나눴을 때 그 나머지 부분도 짝수 팰린드롬이어야 한다.

그러면 앞에서부터 최초 지점에서 불가능한 경우 그 이후 지점에서 가능한 경우가 있을까?
예를 들어 (1 5 5 1) x x x x -> 이게 불가능한 경우 (1 5 5 1 x x) x x가 가능한 경우가 있을까?

결론부터 말하자면, 그런 경우는 절대 없다.

1 5 5 1이 최초 지점이라고 했을 때 이를 연장한다는 것은 또 다른 팰린드롬을 추가하는 것이다.
즉, 연장하게 된다면 1 5 5 1 xx.. 1 5 5 1 인 것이고, 가운데 xx.. 또한 팰린드롬이다.

그래서 이 최초 지점이 불가능한 경우에는 그 이후도 당연히 불가능하고 최대한 많이 나누기 위해서는 짧은 길이로 구성해야 하는데 그 구간이 최초 지점인 것이다.
ex) (1 5 5 1 xx.. 1 5 5 1) -> (1 5 5 1), (xx..), (1 5 5 1)

이를 증명했다면, 구현은 쉬워진다. 앞에서부터 하나 하나 짝수 팰린드롬을 만들 수 있는지 체크하고, 만들 수 있다면 만들고, 다음 원소를 체크하면 된다.

나눠지는 부분도 짝수 팰린드롬이어야 하기 때문에 마지막 원소가 팰린드롬에 포함되어야 한다. 그래서 끝까지 만들어지는지 체크하고, 그에 맞게 출력해 주면 된다.

N <= 5000이기 때문에 워스트 케이스의 경우 O(N^2)도 되지 않는다. (그냥 대략적으로 계산)

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] A;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        ArrayList<Integer> list = new ArrayList<>();
        int i = 0;
        int cnt = 0;
        while(i < N) {
            if(list.size() == 0) {
                list.add(A[i]);
                i += 1;
            } else {
                int newInd = checkPalin(list, i);
                if(newInd == i) {
                    list.add(A[i]);
                    i += 1;
                } else {
                    //팰린드롬을 찾은거임
                    // System.out.println("??");
                    list = new ArrayList<>();
                    i = newInd;
                    cnt += 1;
                }
            }
        }
        if(list.size() == 0) {
            System.out.println(cnt);
        } else {
            System.out.println(-1);
        }
        
    }
    
    static int checkPalin(ArrayList<Integer> list, int startInd) {
        if(list.size() <= (N - 1) - startInd + 1) {
            for(int i=startInd; i < startInd + list.size(); i++) {
                if(A[i] != list.get((list.size() - 1) - (i - startInd))) {
                    return startInd;
                }
            }
            return startInd + list.size() - 1 + 1;
        }
        return startInd;
    }
}