[JAVA] BOJ 16161 가장 긴 증가하는 팰린드롬 수열

백준 16161 가장 긴 증가하는 팰린드롬 수열

입력

수열의 길이는 최대 10^5 -> int
수열의 원소 크기는 최대 10^9 -> long

출력

출력은 딱 한개만 나오니까 system.out.println을 써도 될 것 같다.

풀이

증가하는 팰린드롬 수열이기 때문에 오히려 탐색이 간단하다.

투 포인터를 이용해서 start는 탐색 시작 위치에, end는 탐색 종료 위치에 둔다.

1. 들어오는 원소가 이전 원소보다 크면 end 포인터를 이동한다.
2. 들어오는 원소가 이전 원소보다 작거나 같으면, start부터 end까지 수열이 팰린드롬인지 체크한다.

• 두 원소가 같다면 수열의 길이 2배만큼, 두 원소가 다르다면 수열의 길이-1의 2배만큼 수열을 탐색하여 팰린드롬인지 체크한다.
• 두 원소가 같다면 짝수 길이 팰린드롬으로, 두 원소가 다르다면 홀수 길이 팰린드롬으로 체크해야 한다.

3. 탐색한 문자열 중 가장 긴 팰린드롬 길이를 localLen에 저장하고, maxLen보다 크다면 갱신한다.
4. end 포인터를 다음으로 이동시키고, start도 end와 같은 자리로 이동한다.

• 증가하는 팰린드롬 수열에서, 팰린드롬 안에 서브 팰린드롬은 존재하지 않으며, 두 팰린드롬이 겹쳐서 위치하지 않는다는 것도 기억하자.
• 앞에서 탐색한 수열은 더이상 고려할 가치가 없다. 탐색한 수열 바로 다음부터 다시 탐색한다.

코드

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

public class Main {
    
	private static int N = 0;
	private static int maxLen = 1;
	private static int localLen = 0;
	private static int start = 0;
	private static int end = 0;
	private static long[] arr;

	public static void main(String[] args) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
        
		arr = new long[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<N; i++){
			arr[i] =Long.parseLong(st.nextToken());			
		}

		while (start <= end && end < N - 1) {
			if (arr[end] < arr[end + 1]) { 
				end++;
			} else if (arr[end] == arr[end + 1]) {
				isEvenPalindrome();
				maxLen = Math.max(maxLen, 2 * localLen);
				start = end + 1;
				end++;
			} else {
				isOddPalindrome();
				maxLen = Math.max(maxLen, 2 * localLen + 1);
				start = end + 1;
				end += 1;

			}

		}

		System.out.println(maxLen);
	}
	
	public static void isEvenPalindrome(){
		for (localLen = 0; localLen <= end - start; localLen++) {
			if (end + 1 + localLen >= N || arr[end - localLen] != arr[end + 1 + localLen]) {
				break;
			}
		}
	}
	
	public static void isOddPalindrome(){
		for (localLen = 0; localLen <end - start; localLen++) {
			if (end + 1 + localLen >= N || arr[end - 1 - localLen] != arr[end + 1 + localLen]) {
				break;
			}
		}
	}

}

long[] 대신 ArrayList로 시도

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

public class Main {
    
	private static int N = 0;
	private static int maxLen = 1;
	private static int localLen = 0;
	private static int start = 0;
	private static int end = 0;
	private static long[] arr;
	private static ArrayList<Long> list;

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
        
		list = new ArrayList<Long>(N*2);
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<N; i++){
			list.add(Long.parseLong(st.nextToken()));			
		}

		while (start <= end && end < N - 1) {
            try{
			if (list.get(end) < list.get(end + 1)) { 
				end++;
			} else if (list.get(end).equals(list.get(end + 1))) {
				isEvenPalindrome();
				maxLen = Math.max(maxLen, 2 * localLen);
				start = end + 1;
				end++;
			} else {
				isOddPalindrome();
				maxLen = Math.max(maxLen, 2 * localLen + 1);
				start = end + 1;
				end += 1;

			}
            }catch(Exception e){
                break;
            }

		}

		System.out.println(maxLen);
	}
	
	public static void isEvenPalindrome(){
        try{
		for (localLen = 0; localLen <= end - start; localLen++) {
			if (end + localLen > N || !(list.get(end - localLen).equals(list.get(end + 1 + localLen)))) {
				break;
			}
		}
        }catch(Exception e){
            return;
        }
	}
	
	public static void isOddPalindrome(){
        try{
		for (localLen = 0; localLen <end - start; localLen++) {
			if (end + localLen > N || !(list.get(end - 1 - localLen).equals(list.get(end + 1 + localLen)))) {
				break;
			}
		}
        }catch(Exception e){
            return;
        }
	}

}

• list collection의 get 반환타입은 collection이다. ==이 아니라 equals로 값을 비교해줘야 한다.
• long[]과 다르게 ArrayList에서는 IndexOutOfBoundException이 떠서 try-catch 처리를 해줬다. 로직은 완전히 동일한데 뭐가 문제인걸까?
• ArrayList 크기를 넉넉하게 잡으면 속도가 runtime이 조금 줄어든다.
• long[]이 ArrayList보다 속도와 메모리에서 모두 나았다.