BOJ G4 10942 팰린드롬? JAVA

10942번: 팰린드롬?

---

문제 읽기

일단 맨 처음에 문제를 읽었을 때는 투포인터가 생각났다. 구간을 입력 받을때마다 투포인터를 사용해서 팰린드롬인지 아닌지 판단하는 방식이다. 일단 코드를 빠르게 짜긴 했는데, 제출은 안했었다.

 

문제 입력의 크기를 봤다. N은 2000까지, 숫자는 100,000까지, 질문의 개수 M은 1,000,000까지 가능했다.

만약 맨 처음 푼 방식대로 제출했다면 시간 초과가 나왔을 것이다. 시간 복잡도가 M * N이 되기 때문에 제한 시간인 0.5초는 거뜬히 넘을 것 같다.

 

그렇게 생각하고 한 번 제출해봤는데 왜 되징..?

위에 다시 제출한 게 투포인터 방식이다.

음.. 아마도 중간에 중단된 게 많았나보다.

아 밑에 따로 보니까 자바는 2.5초까지 봐준다.. 이거 덕분인 거 같다.

 

그래도 일단 더 빠르고 확실한 방법이 더 생각나서 그 방식으로 풀었다. 그게 맨 처음에 낸 것이다.

---

문제 풀기

그 방식은 DP이다. 코드를 짜면서 ‘아 뭔가 DP같은데..’라는 느낌이 들었고, 직접 그려봤다.

확실히 그리니까 와 닿았다. DP로 확신하고 문제를 해결했다.

 

우선 숫자의 개수가 홀수 개일 때와 짝수 개일 때를 각각 나눠서 생각했다.

 

홀수 개일 때는, 가운데 하나는 두고 그 양옆으로 뻗어나가면서 같은지 비교하면 되었다.

짝수 개일 때는, 가운데 두 개부터 양 옆으로 뻗어나가면서 같은지 비교하면 된다.

 

결국 짝수던 홀수던 다음과 같이 정리가 가능하다.

1. 처음과 끝이 같은가?
2. 처음과 끝을 제외한 내부가 팰린드롬인가?

이를 이용해서 표를 채웠다.

 

위에서 각 행렬이 나타내는 바는 다음과 같다.

i : start. 팰린드롬의 시작
j : end. 팰린드롬의 끝

DP[i][j] : i~j 사이의 수열이 팰린드롬인가

 

점화식을 정리하면,

DP[i][j] = (nums[i] == nums[j]) && (DP[i+1][j-1])

 

또한 DP[i][j]를 구하기 위해서는 DP[i+1][j-1] 값이 필요하기 때문에, 아래 코드와 같이 j먼저 증가하고, i는 그 안에서 감소하는 형태로 반복문을 구성했다.

---

애매한 부분

숫자의 범위가 100,000인데…

예제에서는 다 한 자릿수 숫자만 주어졌다. 하지만 숫자의 범위가 6자리까지 가능하기 때문에 다음과 같은 수들이 주어지면 이건 팰린드롬으로 쳐야 하는지, 아닌건지 애매했다.

123, 321

 

숫자가 같다/다르다 라고만 생각하면 팰린드롬이 아닌것이고.. 숫자의 배열만 본다 하면 이어서 보면 ‘123321’이기 때문에 팰린드롬이다.

 

문제에 이게 명확하지 않아서 질문게시판을 봤는데 나랑 비슷한 고민을 하는 사람들이 있었다. 결국엔 이건 ‘팰린드롬이 아니다’.

 

사실 이건 문제에서 명시해줘야 한다. 그런데 문제에서는 그냥..

‘… S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지 …’

 

라고 되어 있어서 애매했다.

 

어쨌든 이건 아니라고 보고 해결하면 될 거 같다.

---

코드 - DP

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_G4_10942_펠린드롬 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        int[] nums = new int[N];
        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < N; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        //dp?
        boolean[][] dp = new boolean[N][N];
        for (int j = 0; j < N; j++){
            for (int i = j; i >= 0; i--){
                //1자리일 때
                if (i == j) dp[i][j] = true;
                //처음과 끝이 같은지, 내부가 팰린드롬인지 파악
                else if (nums[i] == nums[j]) {
                    if (j - i == 1) dp[i][j] = true;
                        //두 자리 이상인 경우 내부가 펠린드롬인지 체크
                    else if (dp[i + 1][j - 1]) dp[i][j] = true;
                }
            }
        }

        int M = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        while(M-- > 0){
            st = new StringTokenizer(in.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            sb.append((dp[s-1][e-1])? 1 : 0).append("\\n");
        }
        System.out.println(sb);
    }
}

참고 코드 - 투포인터 - 정답은 맞음

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_G4_10942_펠린드롬 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        int[] nums = new int[N];
        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < N; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        while(M-- > 0){
            st = new StringTokenizer(in.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            //펠린드롬일까? idx : s-1 ~ e-1
            int start = s-1;
            int end = e-1;
            boolean isTrue = true;
            while(true){
                if (start >= end) break;

                if (nums[start] != nums[end]){
                    isTrue = false;
                    break;
                }
                start++;
                end--;
            }

            sb.append((isTrue)? 1 : 0).append("\\n");
        }
        System.out.println(sb);
    }
}