[백준] 1709번 Java (문자열, 투포인터)

https://www.acmicpc.net/problem/17609

💡문제

풀이

접근법 : 팰린드롬 문제를 조금 응용해서 풀면 된다.

회문 : 'abba'나 'reviver' 처럼 앞 뒤 방향이 같은 순서의 문자로 구성된 문자열이다.

유사 회문 : 한 문자를 삭제하면 회문이 된다.

투포인터를 이용해서 회문인지를 구하고, 회문이 아니라면 유사회문인지 확인한다.

<회문 확인>

 private static boolean isPalindrome(String str, int left, int right) {
        while (left < right) {
            if (str.charAt(left) == str.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }

• 왼쪽 포인터와 오른쪽 포인터가 같으면 양쪽을 동시에 움직인다.
• 같지 않으면 회문이 아니다.

<유사 회문 확인>

private static boolean isPseudoPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return isPalindrome(str, left + 1, right) || isPalindrome(str, left, right - 1);
            }
            left++;
            right--;
        }
        return false;
    }

• 왼쪽과 오른쪽이 같지 않으면 포인터를 하나 움직인 뒤 회문인지 확인해본다.
• 즉, 포인터를 하나 움직여서 하나의 문자를 건너뛰면 회문이 되는지 확인하는 것이다.
• 왼쪽과 오른쪽 둘 다 삭제할 수 있으므로 둘 중 하나라도 회문이면 유사 회문이 된다.

<출력 부분>

for (int i = 0; i < n; i++) {
            String str = br.readLine();
            if (isPalindrome(str, 0, str.length() - 1)) {
                bw.write(0 + "\n");
            } else if (isPseudoPalindrome(str)) {
                bw.write(1 + "\n");
            } else {
                bw.write(2 + "\n");
            }
        }
        bw.flush();
        bw.close();

• 회문인지 먼저 확인한 뒤, 회문이 아닌 경우를 돌린다.

내 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            if (isPalindrome(str, 0, str.length() - 1)) {
                bw.write(0 + "\n");
            } else if (isPseudoPalindrome(str)) {
                bw.write(1 + "\n");
            } else {
                bw.write(2 + "\n");
            }
        }
        bw.flush();
        bw.close();
    }

    private static boolean isPalindrome(String str, int left, int right) {
        while (left < right) {
            if (str.charAt(left) == str.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }

    private static boolean isPseudoPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return isPalindrome(str, left + 1, right) || isPalindrome(str, left, right - 1);
            }
            left++;
            right--;
        }
        return false;
    }

}