[백준 10942] 팰린드롬?

글에 개요

백준 알고리즘 10942번 "팰린드롬?" 문제입니다.

이 문제는 팰린드롬이 무엇인지에 대해 알아 볼 수 있는 문제이며, DP를 활용해 시간 초과의 이슈를 해결하는 것이 중요합니다.

팰린드롬 또한 대기업의 알고리즘 SW TEST에도 기본적으로 활용되기 때문에 꼭 풀어보는 것을 추천드립니다.

혹시 어느 곳에서 나왔는지 궁금하신 분은 댓글로 남겨주시면 따로 알려드리겠습니다!!

[백준 10942] 팰린드롬?: https://www.acmicpc.net/problem/10942

참고 내용

팰린드롬 : 뒤집어서 읽어도 똑같이 읽히는 형태를 말합니다.

1 2 2 1
1 3 3 1
1 2 3 2 1

l~3 line에 있는 모든 숫자들은 팰린드롬이라고 말할 수 있는 것이죠!!

[팰린드롬 구현 코드]

public static boolean isPalindrome(int[] array, int s, int e) {
    while(s < e) {
        if(array[s++] != array[e--]) {
            return false;
        }
    }
    return true;
}

▷ 단순하게 시작지점에서 중간지점까지 한 번이라도 비교값이 다르지 않다면 팰린드롬이 될 것입니다.

▷ 하지만, 이 방식은 모든 경우를 다 찾아보는 형태이므로, 효율적이지는 못합니다.

핵심 내용

1. 팰린드롬인지 확인하는 시간 : O(N), 질문이 M개일 때 처리 시간 : O(MN)이므로 효율화를 위해 DP로 해결한다.
2. 왼쪽 끝과 오른쪽 끝이 같다면, 그 사이의 숫자가 팰린드롬이라면, 이 숫자는 팰린드롬이 된다.
3. Bottom-Up 방식으로 해결

해결 방법

1. 팰린드롬인지를 파악하는 answerAry를 초기화 해준다.
1. 한 자리 숫자는 무조건 팰린드롬이므로 TRUE
2. 두 자리 숫자는 숫자가 같아야 팰린드롬 (맨 앞과 맨 뒤가 같다는 가정하에 시작하므로 두 자리까지는 초기화!!)
2. makeAnswerAry를 통해 길이가 3부터 검사해주면 됩니다.
1. 1~3까지나 3~1까지나 답은 똑같기 때문에 같은 값을 넣어주면 됩니다.

해결한 코드

	import java.util.Scanner;
	public class Main {
	public static boolean[][] answerAry;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] inputAry = new int[n+1];
	for(int i = 1; i <= n; i++) {
	inputAry[i] = sc.nextInt();
	}
	answerAry = new boolean[n+1][n+1];
	for(int i = 1; i <= n; i++) {
	answerAry[i][i] = true;
	}
	for(int i = 1; i < n; i++) {
	if(inputAry[i] == inputAry[i+1])
	answerAry[i][i+1] = answerAry[i+1][i] = true;
	}
	makeAnswerAry(inputAry, n);
	int testCase = sc.nextInt();
	for(int i = 0; i < testCase; i++) {
	int start = sc.nextInt();
	int end = sc.nextInt();
	int answer = 0;
	if(answerAry[start][end])
	answer = 1;
	System.out.println(answer);
	}
	}
	public static void makeAnswerAry(int[] inputAry, int n) {
	for(int i = 2; i < n; i++) {
	for(int j = 1; j <= n - i; j++) {
	if(inputAry[j] == inputAry[j+i] && answerAry[j+1][j+i-1]) {
	answerAry[j][j+i] = answerAry[j+i][j] = true;
	}
	}
	}
	}
	}

view raw B_10942.java hosted with ❤ by GitHub

백준 내용 참고

팰린드롬?

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5 초	256 MB	9307	2748	1639	30.556%

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

예제 입력 1 

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

예제 출력 1 

1
0
1
1