백준 10942번 팰린드롬? :: 마이구미

이번 글은 백준 알고리즘 문제 10942번 팰린드롬? 을 다뤄본다.

로켓처럼 빠른 회사인 쿠* 개발자 코딩 테스트에서 출제된 문제이기도 하다.

문제 풀이의 최적의 접근법은 동적계획법이다.

여기서는 동적계획법과 순수한 다른 방법을 다룬다.

팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다

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

먼저, 홍준이는 자연수 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개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

정말 단순하게 생각해도 이 문제를 풀 수 있다.

왼쪽 오른쪽 끝을 기준으로 중간으로 이동하면서 비교하는 방식이다.

1 2 3 2 1
1 2 3 2 1

1 2 2 1
1 2 2 1

위와 같이 끝과 끝에서 중간으로 이동하면서 비교한다.

비교하면서, 중간 지점이 올때까지, 비교 값들이 계속해서 같다면, 팰린드롬이다.

그렇지 않고, 한번이라도 비교 값이 다르다면, 팰린드롬이 아니게 된다.

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

코드로는 위와 같이 구현될 수 있다.

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

조금만 생각해봐도, 부분적인 답을 활용하여 전체의 답을 구할 수 있다.

즉, 동적계획법을 활용하여 효율적이게 접근할 수 있다.

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

위 예시에서, 왼쪽 끝과 오른쪽 끝이 같다면, 그 사이의 숫자가 팰린드롬이라면, 이 숫자는 팰린드롬이 된다.

첫번째 방법처럼, 하나하나 이동하면서 비교할 필요가 없고, 그 사이의 수가 팰린드롬인지 판단하면 된다.

dp[s][e] = s부터 e까지 팰린드롬인지 아닌지
dp[s][e] = array[s] == array[e] && dp[s + 1][e - 1]

// i는 거리 s에서 e까지 길이
for (int i = 2; i <= n - 1; i++) {

    for (int j = 1; j <= n - i; j++) {
        if (array[j] == array[j + i] && dp[j + 1][j + i - 1]) {
            dp[j][j + i] = true;
        }
    }

}

루프의 기본적인 흐름은 아래와 같다.

i = 1 길이 = 2
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1

i = 2 길이 = 3
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1

i = 3 길이 = 4
1 2 3 2 1
1 2 3 2 1

위와 같이 길이순으로 루프를 돌면서, 계산된 값을 이용하게 되는 메모라이즈 방식을 구현할 수 있다.

본인의 경우 길이가 1일때와 2일 때는 먼저 계산하였다.

1일때는 무조건 팰린드롬이고, 길이가 2일 때는, 두 수가 같으면 팰린드롬이기 때문이다.

for (int i = 1; i <= n; i++) {
    dp[i][i] = true;
    if (array[i] == array[i - 1]) {
        dp[i - 1][i] = true;
    }
}

자세한 건 아래 Github URL의 전체 코드를 참고하길 바란다.

백준 알고리즘 문제 10942번 "팰린드롬?" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/dp/10942.java