[BOJ] 백준 17609 - 회문 풀이

1. 문제

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

17609번: 회문

 

2. 풀이

백준 문자열 파트 골드 5의 문제이다.
처음 문제를 보고 문제가 쉽게 느껴져서 입력으로 주어진 문자열을 StringBuffer에 넣고 reverse() 함수를 통해 돌린 후 회문이면 "0"을 회문이 아니라면 문자를 하나씩 제거하면서 회문인지 체크하는 방식으로 풀었다.

그 결과 당연히 시간 초과가 났다...  (최악의 경우 100,000자리가 나온다면 반복문을 10만번 돌아야 한다...)
그 후 Two Point라는 힌트와 다른 분의 풀이를 참고하여 문제를 해결하였다.

우선 StringBuffer에 넣고 reverse() 함수를 쓰는 부분을 변경했다.
문자열을 입력받은 후 left 포인트, right 포인트를 설정하고 왼쪽 끝과 오른쪽 끝에서 차례로 내려오면서 문자열을 비교하는 함수를 만들어 실행했다. (35줄, 편의를 위해 회문 함수라고 부른다.) 실행 후 회문이면 그대로 0을 출력한다.

만약 회문이 아니라면 NotPalindrome 함수를 실행한다.
이 함수는 회문 함수와 동일하게 왼쪽 끝과 오른쪽 끝에서 차례로 내려오면서 문자열을 비교한다. 이때 서로 다른 문자가 발견된다면 왼쪽 문자를 제거하고 회문 함수 실행, 오른쪽 문자를 제거하고 회문 함수 실행, 총 두 번의 회문 함수를 추가로 실행한다. (50줄, 51줄) 이러면 reverse() 함수를 쓰지 않아도 특정 문자를 제거하고 회문인지를 체크할 수 있다. 그 후 두 개의 flag가 모두 거짓이면 "2"를, 하나라도 참이 있다면 "1"을 출력한다.

 

3. 소스 코드

<시간 초과 코드>

import java.io.*;

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));
        StringBuffer sb = new StringBuffer();
        boolean flag = true;

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            String input = br.readLine();
            String reverseInput = sb.append(input).reverse().toString();

            // 회문이면
            if (input.equals(reverseInput)) {
                bw.write("0" + "\n");
                sb.delete(0, sb.length());
                continue;
            } else {
                for (int j = 0; j < reverseInput.length(); j++) {
                    sb.delete(0, sb.length());

                    String replaceEnconunter = input.substring(0, j) + input.substring(j + 1, input.length());
                    String replaceReverse = sb.append(replaceEnconunter).reverse().toString();

                    if (replaceReverse.equals(replaceEnconunter)) {
                        bw.write("1" + "\n");
                        flag = false;
                        break;
                    }
                }
            }

            if (flag) {
                bw.write("2" + "\n");
            }

            flag = true;
            sb.delete(0, sb.length());
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

< 정답 코드>

import java.io.*;

public class Main {

    static String input;
    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 T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            input = br.readLine();
            int left = 0;
            int right = input.length() - 1;

            // 회문이면
            if (Palindrome(left, right)) {
                bw.write("0" + "\n");
                continue;
            }

            if (NotPalindrome(left, right)) {
                bw.write("1" + "\n");
            } else {
                bw.write("2" + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // 회문인지 검사
    private static boolean Palindrome(int left, int right) {
        while(left <= right) {
            if (input.charAt(left) != input.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // 회문이 아닐때
    private static boolean NotPalindrome(int left, int right) {
        while(left <= right) {
            if(input.charAt(left) != input.charAt(right)) {
                boolean leftDelete = Palindrome(left + 1,right);
                boolean rightDelete = Palindrome(left,right - 1);

                if(leftDelete == false && rightDelete == false) {
                    return false;
                } else {
                    return true;
                }
            }
            left++;
            right--;
        }
        return true;
    }
}