[BaekJoon] 16161 가장 긴 증가하는 팰린드롬 부분수열 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int seriesCnt;
    static int[] series;

    static void input() {
        Reader scanner = new Reader();

        seriesCnt = scanner.nextInt();
        series = new int[seriesCnt];

        for(int idx = 0; idx < seriesCnt; idx++) {
            series[idx] = scanner.nextInt();
        }
    }

    /*
     * 증가하는 팰린드롬 중 가장 긴 팰린드롬을 찾아야 한다
     * 증가하는 팰린드롬은 중간부분을 기점으로 왼쪽으로는 증가, 오른쪽으로는 감소하게 된다
     * 이를 이용하여 투포인터 알고리즘을 통해 증가하는 수열을 찾고, 감소하거나 같아지는 순간이 생길 때 증가하는 팰린드롬이 되는지 확인한다
     *  - 투 포인터에서 왼쪽 포인터를 leftPtr, 오른쪽 포인터를 rightPtr이라고 할 때, leftPtr은 고정한 상태로 rightPtr을 우선 움직인다
     *      1. rightPtr번째 수보다 rightPtr + 1번째 수가 더 클 경우
     *          - 증가하는 수열이니 rightPtr을 1씩 옮긴다
     *      2. rightPtr번째 수와 rightPtr + 1번재 수가 같을 경우
     *          - 두 수가 중간부분에 해당하는 두 수가 될 것이다
     *          - 그렇다면 왼쪽 중간 부분의 왼쪽 수들과 오른쪽 중간 부분의 오른쪽 수들이 팰린드롬을 이루는지 확인한다
     *          - 처음으로 양쪽 수가 달라지는 시점 이전까지가 팰린드롬이기 때문에 이를 구해 최대 길이를 갱신한다
     *      3. rightPtr번째 수가 rightPtr + 1번째 수보다 큰 경우
     *          - rightPtr번째 수가 중간 부분이 될 것이다
     *          - 그렇기 때문에 rightPtr번째 수 왼쪽 수들과 오른쪽 수들이 팰린드롬을 이루는지 확인한다
     *          - 처음으로 양쪽 수가 달라지는 시점 이전까지가 팰린드롬이기 때문에 이를 구해 최대 길이를 갱신한다
     */
    static void solution() {
        System.out.println(twoPointer(0, 0));
    }

    static int twoPointer(int leftPtr, int rightPtr) {
        int answer = 1;

        while(leftPtr <= rightPtr && rightPtr < seriesCnt - 1) {
            if(series[rightPtr] < series[rightPtr + 1]) {
                rightPtr++;
                continue;
            }
            if(series[rightPtr] == series[rightPtr + 1]) {
                int halfLen = 0;
                for(halfLen = 0; halfLen <= rightPtr - leftPtr; halfLen++) {
                    if((rightPtr + 1) + halfLen >= seriesCnt) {
                        break;
                    }
                    if(series[rightPtr - halfLen] != series[(rightPtr + 1) + halfLen]) {
                        break;
                    }
                }

                answer = Math.max(answer, halfLen * 2);
                leftPtr = rightPtr + 1;
                rightPtr++;
                continue;
            }
            if(series[rightPtr] > series[rightPtr + 1]) {
                int halfLen = 0;
                for(halfLen = 0; halfLen < rightPtr - leftPtr; halfLen++) {
                    if((rightPtr + 1) + halfLen >= seriesCnt) {
                        break;
                    }
                    if(series[(rightPtr - 1) - halfLen] != series[(rightPtr + 1) + halfLen]) {
                        break;
                    }
                }

                answer = Math.max(answer, halfLen * 2 + 1);
                leftPtr = rightPtr + 1;
                rightPtr++;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}