백준 16161 가장 긴 증가하는 팰린드롬 부분수열
https://www.acmicpc.net/problem/16161
16161번: 가장 긴 증가하는 팰린드롬 부분수열
팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드��
www.acmicpc.net
주어진 수열의 모든 연속 부분수열를 탐색하는 경우수는 O(N^2)이고, 그 부분수열이 팰린드롬인지 판별하는데 걸리는 시간이 O(N)이므로 시간 복잡도가 총 O(N^3)이다. N=10만이기 때문에 1000조의 계산수를 감당할 수 없다.
하지만, 증가한다는 특성 그리고 팰린드롬의 특성을 이용하면 탐색 경우수를 크게 줄일 수 있다.
다음과 같은 수열이 주어진다고 생각해보자
3 2 7 7 5 8 6
모든 부분수열 갯수는 7+6+5+4+3+2+1 = 28개다.
앞의 (3 2) 를 생각보자. (3 2) 는 이미 증가한다는 특성을 위배했다. 그러므로
(3 2) 가 포함된 부분 수열은 생각할 필요가 없다.
마찬가지로 (2 7 7 5) 을 생각해보자.
(2 7 7 5) 는 팰린드롬이 아니다. 그러므로 앞뒤로 어떤 문자고 오든간에 팰린드롬이 될수 없다.
그러므로 (2 7 7 5)가 포함된 부분 수열은 생각할 필요가 없다.
이 특성을 이용하여 투 포인터를 이용해서 풀어본다
다음과 같은 수열이 주어진다고 생각해보자
1 5 7 9 7 1 2 4 6 8 6
1) L= 0 R = 1로 두 포인터의 위치를 초기화한다.
L R
0 1
1 5 7 9 7 1 2 4 6 8 6
2) A[R]< A[R+1] 이면 증가 수열이므로 R을 한칸 옮긴다.
L R
0 2
1 5 7 9 7 1 2 4 6 8 6
3) A[R]< A[R+1] 이면 증가 수열이므로 R을 한칸 옮긴다.
L R
0 3
1 5 7 9 7 1 2 4 6 8 6
4) A[R] > A[R+1] 이면 [L : R + R- L] 이 팰린드롬인지 확인한다.
팰린드롬이 아니라면 그지점에 L,R을 둔다.
예제에서는 7 9 7 까지는 팰린드롬이지만 5 7 9 7 1이 팰린드롬이 아니므로
L,R를 1이 있는 위치 5로 옮긴다.
이때까지 최대 길이 부분 수열 팰린드롬의 길이는 3이다.
L,R
5
1 5 7 9 7 1 2 4 6 8 6
5) A[R] < A[R+1] 이므로 R를 한칸 위로 옮긴다.
L R
5 6
1 5 7 9 7 1 2 4 6 8 6
6) A[R] < A[R+1] 이므로 R를 한칸 위로 옮긴다.
L R
5 7
1 5 7 9 7 1 2 4 6 8 6
7) A[R] < A[R+1] 이므로 R를 한칸 위로 옮긴다.
L R
5 8
1 5 7 9 7 1 2 4 6 8 6
7) A[R] < A[R+1] 이므로 R를 한칸 위로 옮긴다.
L R
5 9
1 5 7 9 7 1 2 4 6 8 6
8) 7) A[R] > A[R+1] 이므로 [L : R + R- L]이 팰린드롬인지 확인한다.
6 8 6 까지는 팰린드롬이라는 것을 알수 있고,
수열이 끝났으므로 리턴된다.
L R
5 9
1 5 7 9 7 1 2 4 6 8 6
이렇듯 투포인터를 이용해서 풀면 수열 탐색양을 크게 줄일 수 있으므로 시간안에 문제를 풀수 있다.
package 백준;
import java.util.*;
import java.io.*;
public class 가장긴증가하는팰린드롬부분수열 {
public static class MyScanner {
BufferedReader bf;
StringTokenizer st;
MyScanner() {
bf = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(bf.readLine());
} catch (Exception e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MyScanner sc = new MyScanner();
int N = sc.nextInt();
long arr[] = new long[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.nextLong();
}
int l = 0;
int r = 0;
int answer = 1;
while (l <= r && r < N - 1) {
if (arr[r] < arr[r + 1]) { // 증가하는 부분수열 R 포인트 한칸 오른쪽으로
r++;
} else if (arr[r] == arr[r + 1]) { // check if palindrome l~ l + 2* (r -l) is palindrome
int t = 0;
for (t = 0; t <= r - l; t++) {
if (r + 1 + t >= N || arr[r - t] != arr[r + 1 + t]) {
break;
}
}
answer = Math.max(answer, 2 * t);
l = r + 1;
r++;
} else { // check if palindrome l~ l + 2* (r -l) is palindrome
int t = 0;
for (t = 0; t < r - l; t++) {
if (r + 1 + t >= N || arr[r - 1 - t] != arr[r + 1 + t]) {
break;
}
}
answer = Math.max(answer, 2 * t + 1);
l = r + 1;
r += 1;
}
}
System.out.println(answer);
}
}