boj 10942: 팰린드롬?

어떤 문자열이 팰린드롬인지 확인하는 2가지 방법 --> O(N)

• s == reverse(s) 인지 확인
• 모든 ch[i] == ch[s.length-i] 인지 확인

이 때, 쿼리의 갯수가 M개이므로 총 걸리는 시간은 O(MN)인데 시간 제한에 걸린다.

 

팰린드롬을 검사하는 다른 방법

1. 길이가 1인 부분 수열은 반드시 팰린드롬 --> O(N)
2. 길이가 2인 부분 수열은 두 수가 같을 때만 팰린드롬 --> O(N)
3. 길이가 3이상인 경우는 DP를 이용한다.-->O(N^2)
   1. DP[i][j]: i ~ j까지 팰린드롬인지 아닌지 저장
   2. ch[i] == ch[j]이면 DP[i][j] = DP[i+1][j-1]이다.

=> O(N^2+M)만에 구할 수 있다.

 

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int dp[][] = new int[n + 1][n + 1];

		dp = calcPalindrome(arr, n);

		int m = Integer.parseInt(br.readLine());
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			bw.write(dp[start][end] + "\n");
		}
		bw.flush();
		bw.close();
	}

	public static int[][] calcPalindrome(int arr[], int n) {
		int dp[][] = new int[n + 1][n + 1];

		// 길이가 1일 때
		for (int i = 1; i <= n; i++) {
			dp[i][i] = 1;
		}

		// 길이가 2일 때
		for (int i = 1; i <= n - 1; i++) {
			if (arr[i] == arr[i + 1]) {
				dp[i][i + 1] = 1;
			}
		}

		// 길이가 3 이상
		for (int i = 3; i <= n; i++) {
			for (int j = 1; j <= n - i + 1; j++) {
				int k = j + i - 1;
				if (arr[j] == arr[k] && dp[j + 1][k - 1] == 1) {
					dp[j][k] = 1;
				}
			}
		}

		return dp;
	}
}