[Java] 백준 BOJ / 10942번: 펠린드롬?

펠린드롬?

문제

---

문제 설명

숫자로 이루어진 배열이 주어지고 해당 배열의 시작과 끝이 주어졌을 때 그만큼의 부분 수열이 좌우대칭인 펠린드롬인지 판별하는 문제이다.

---

첫번째 구현

처음엔 그냥 isPalindrome 이라는 함수를 구현하여 문제에서 주어지는 s 값과 e 값을 이용하여 substring 한 값을 넘겨주고 대칭인지 확인 하는 함수를 구현하였다.

while (m-- > 0) {
	st = new StringTokenizer(br.readLine());
	s = Integer.parseInt(st.nextToken());
	e = Integer.parseInt(st.nextToken());

	String subString = str.substring(s - 1, e);
	sb.append(isPalindrome(subString)).append('\n');
}

public static int isPalindrome(String str) {
	int left = 0;
	int right = str.length() - 1;

	while (left < right) {
		if (str.charAt(left) != str.charAt(right)) {
			return 0;
		}
		left++;
		right--;
	}
	return 1;
}

이렇게 풀었더니 결과는 틀렸다.

내가 푼 문제의 시간 복잡도를 구해보면

substring(s - 1, e) 은 새로운 문자열을 생성하는 과정이기 때문에 O(n) 이 걸린다.
그리고 isPalindrome() 문자열을 검사하는 과정도 O(n) 이 소요된다.

따라서, 질문이 총 M개가 주어지기 때문에 최종 시간 복잡도는 O(n * m) 이고
문제의 조건에 따라 최악의 경우 O(n * m) = 1,000,000,000 이다.

이 문제에서 주어진 시간은 Java의 경우 2.5 초인데 이러면 250,000,000 안에 연산을 끝내야 한다.

그래서 DP를 활용하기로 했다.

---

두번째 구현

boolean 타입으로 선언된 2차원의 DP 배열을 사용한다.

문제에서 주어지는 배열이 Palindrome인지 판별하는데, 두 가지 특수한 상황이 있다.

1. 길이가 1일 경우 → 항상 펠린드롬
   길이가 1인 경우 항상 펠린드롬이기 때문에 1부터 n까지 모두 true 로 초기화해준다.

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

2. 길이가 2일 경우 → 연속된 2개의 수의 값이 같은 경우 펠린드롬
   길이가 2인 경우 연속되는 2개의 수의 값이 같다면 펠린드롬이다.

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

3.길이가 3 이상일 경우

일단 구현된 코드를 먼저 보면 아래와 같다.

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

루프 변수 i 는 2부터 n-1 까지 증가하는데 i는 현재 검사하는 부분 문자열의 길이를 뜻한다.

j는 1부터 n - i 까지 증가하는데 j는 부분 문자열의 시작 인덱스이고 j + i 가 n을 넘으면 안되기 때문에 n - i 까지 증가한다.

조건을 살펴보자

• arr[j] == arr[j+1]
  이 조건은 현재 검사하는 문자열에서 양 끝의 문자가 같은지 확인한다.

• dp[j + 1][j + i - 1]
  이 조건은 양 끝을 제외한 부분이 펠린드롬인지 확인한다.

위 두 조건을 만족하면 해당 배열은 펠린드롬이라고 dp[j][j + i]에 표시를 해준다.

---

코드

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

public class Main_10942 {
    static int n, m;
    static int[] arr;
    static boolean[][] dp;
    static int s, e;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        dp = new boolean[n + 1][n + 1];

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

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

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

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

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

            sb.append(dp[s][e] ? 1 : 0).append('\n');
        }
        System.out.println(sb);
    }
}