[Baekjoon 26110] Palindrome Type - JAVA

[Gold III] Palindrome Type - 26110

문제 링크

성능 요약

메모리: 17504 KB, 시간: 156 ms

분류

재귀, 문자열

문제 설명

A palindrome string is a word which reads the same backward as forward, such as madam or racecar. In this problem we only consider strings with lowercase alphabets.

We newly define the types of palindromes. If a string is not a palindrome, we try to make it a palindrome by removing the minimum number of characters in the string. For a string $w$, if $k$ is the minimum number of characters removed to make the string a palindrome, we call the string $w$ type-$k$ palindrome. Thus, if $w$ is a palindrome, then $w$ is a type-$0$ palindrome.

Given a string $w$, write a program to determine if $w$ is a type-$k$ palindrome where $k = 0, 1, 2, 3$.

입력

Your program is to read from standard input. The input is a single line containing a string $w$ with length $n$ ($5 ≤ n ≤ 10^5$) of lowercase alphabets.

출력

Your program is to write to standard output. Print exactly one line. The line should contain a number $k$ among $\{0, 1, 2, 3, -1\}$ if the input string is a type-$k$ palindrome where $k = 0, 1, 2, 3$ and otherwise $-1$. The negative number $-1$ means the input string is not a type-$k$ palindrome where $k = 0, 1, 2, 3$.

문제 풀이

문제를 한글로 요약, 정리하면 아래와 같다.

회문 문제다. 회문이란 - 문자열은 앞으로 읽을 때와 뒤로 읽을 때 동일한 단어를 의미한다.

주어진 문자열을 회문으로 만들기 위해 제거해야 하는 문자의 최소 수를 찾는 문제다.

문자열 $w$에 대해, 회문으로 만들기 위해 제거해야 하는 문자의 최소 수에 따라 type이 바뀐다.

회문이 되기위해 제거해야 하는 수가 $k$라면 해당 문자열 $w$를 type-$k$ 회문이다.

만약, 입력받은 문자열 $w$가 제거하지 않아도 회문이라면 $w$는 type-0 회문이다.

입력받은 문자열 $w$가 type-$k$ 회문인지 여부를 결정하는 프로그램을 작성해야 합니다

제거할 수 있는 문자열을 최대 3개까지 가능하다.

3개 이상 제거를 해야 회문이 되는 경우에는 -1을 출력하면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

        String w = br.readLine().trim();
        int result = checkPalindrome(w, 0);

        bw.write((result < 4) ? String.valueOf(result) : "-1");
        bw.newLine();
        bw.flush();
        bw.close();
    }

    public static int checkPalindrome(String w, int k) {
        if (k > 3) {
            return k;
        }

        int left = 0;
        int right = w.length() - 1;
        while (left < right) {
            if (w.charAt(left) == w.charAt(right)) {
                left++;
                right--;
            } else {
                int option1 = checkPalindrome(w.substring(left + 1, right + 1), k + 1);
                int option2 = checkPalindrome(w.substring(left, right), k + 1);
                return Math.min(option1, option2);
            }
        }

        return k;
    }
}

코드 풀이

String w = br.readLine().trim();

int result = checkPalindrome(w, 0);

bw.write((result < 4) ? String.valueOf(result) : "-1");
bw.newLine();
bw.flush();
bw.close();

• 'w': 입력받을 문자열을 저장할 변수
• result: checkPalindrome를 호출해 문자열을 팰린드롬으로 만들기 위해 필요한 최소 문자 제거 횟수를 저장하는 변수
• 'result'가 4 미만이라면 그 값을 문자열로 변환하여 출력하고, 그렇지 않으면 -1을 출력한다.

public static int checkPalindrome(String w, int k) {
if (k > 3) {
    return k;
}

int left = 0;
int right = w.length() - 1;

• checkPalindrome: 문자열 'w'와 현재까지의 제거 횟수 'k'를 사용해 팰린드롬을 만들기 위한 최소 제거 횟수를 계산하는 메서드
• 'k'가 4보다 큰 경우, 더 이상 문자를 제거할 수 없으므로 'k'를 반환한다.
• left, right: 팰린드롬 검사를 위해 문자열을 양 끝에서부터 비교하는 데 사용하기 위해 문자열의 양 끝 인덱스를 나타낸다.

while (left < right) {
    if (w.charAt(left) == w.charAt(right)) {
    left++;
    right--;
} else {
    int option1 = checkPalindrome(w.substring(left + 1, right + 1), k + 1);
    int option2 = checkPalindrome(w.substring(left, right), k + 1);
    return Math.min(option1, option2);
    }
}
return k;

• 왼쪽에서 시작해서 오른쪽과 만나기 전까지 즉, 교차하기 전까지 반복문을 돌린다.
• 양 끝의 문자가 같으면 다음 문자 쌍으로 이동한다.
• 양 끝의 문자가 다른 경우 옵션 두 가지중 더 작은 횟수를 반환한다.
  1. 왼쪽 문자를 제거하고 팰린드롬을 검사하는 'checkPalindrome'를 호출한 결과인 'option1'
  2. 오른쪽 문자를 제거하고 팰린드롬을 검사하는 'checkPalindrome'를 호출한 결과인 'option2'
• 문자열이 펠린드롬이면 k를 반환한다.