[백준 17609] 회문 (팰린드롬)

팰린드롬이란, 앞 뒤가 똑같은 전화번호 문자열을 말한다고 합니다.

단순히 "abba" 문자열이 팰린드롬인가를 확인한다면, 

[1] 문자열을 거꾸로 뒤집어서 확인하거나

[2] 양끝에 left, right로 커서를 두고 left < right 일때까지 양 끝을 비교해도 되는데요.

 

물론 우리의 알고리즘은 그렇게로만 끝나지 않기 때문에 더 향상된 버전의 팰린드롬을 만날 수 있었습니다.

제 수준에서 풀만한 것들을 먼저 뽑아보았어요..

아래 중에서 하나씩 풀어보려 합니다.

|  백준 팰린드롬 문제 모음

브론즈	1259 팰린드롬수	바로가기
실버	1213 팰린드롬 만들기 1254 팰린드롬 만들기 17609 회문	바로가기 바로가기 바로가기
골드	1053 팰린드롬 공장	바로가기

 

🛎 17609 회문

|  문제 

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

|  입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

|  출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

|  예제 입력

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

|  예제 출력

0
1
1
2
2
0
1

 

⌨️ 코드1 - 반복문

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static int isPanlindrome(char[] arr, int left, int right, int delCnt){

        while (left < right) {
            if (arr[left] == arr[right]) {
                // 회문인 경우
                left++;
                right--;
            } else {
                // 회문이 아닌 경우
                int l2 = left;
                int r2 = right;

                // 좌측 문자를 하나 삭제 후 확인
                l2 += 1;
                while (l2 < r2) {
                    if (arr[l2] == arr[r2]){
                        l2++;
                        r2--;
                    } else {
                        delCnt++;
                        break;
                    }
                }

                if (delCnt == 0) { // abca와 같이 좌측 제거 후 유사회문인 경우 고려
                    return 1;
                }

                // 우측 문자를 하나 삭제 후 확인
                l2 = left;
                r2 = right - 1;
                while (l2 < r2) {
                    if (arr[l2] == arr[r2]){
                        l2++;
                        r2--;
                    } else {
                        delCnt++;
                        break;
                    }
                }

                // 좌우축 모두 확인 후에 delCnt를 반환
                return delCnt; // 반환하지 x면 무한 루프

            }
        }

        return delCnt;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T --> 0) {
            String s = br.readLine();
            sb.append(isPanlindrome(s.toCharArray(), 0, s.length()-1,0));
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }
}

 

⌨️ 코드2 - 재귀

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    // 재귀로 풀 경우
    public static int isPanlindrome2(char[] arr, int left, int right, int delCnt){

        while (left < right) {
            if (arr[left] == arr[right]) {
                // 회문인 경우
                left++;
                right--;
            } else {
                // 처음 불일치한 경우
                if (delCnt == 0) {
                    // 좌우측을 하나씩 삭제한 문자열이 회문인지 확인
                    if (isPanlindrome2(arr, left + 1, right, 1) == 0 ||
                            isPanlindrome2(arr, left, right - 1, 1) == 0) {
                        return 1;
                    } else {
                        return 2;
                    }
                } else {
                    return 2;
                }
            }
        }

        return 0;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T --> 0) {
            String s = br.readLine();
            sb.append(isPanlindrome2(s.toCharArray(), 0, s.length()-1,0));
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }
}