회-문

회-문

 

백준 17609번 문제

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

17609번: 회문

 

 

 

 

 

 

1. 문제

 

 

 

 

 

 

 

 

2. 풀이

2.1 풀이 방법

문자열의 앞과 뒤를 비교하며 회문인지 검사한다.

만약 탐색 중 앞의 문자 또는 뒤의 문자를 지웠을 때, 회문이 될 수 있는 가능성이 있다면 

앞의 문자 또는 뒤의 문자를 지우고, 탐색하지 않은 나머지 문자열이 회문인지를 확인한다.

 

문자열 전체가 회문일 때 0을 반환.

문자를 하나 지웠을 때 나머지 문자열이 회문이 된다면 1을 반환.

문자를 하나 지웠을 대 나머지 문자열이 회문이 되지 않는다면 2를 반환하면 된다.

 

 

 

만약 주어진 문자열이 "abddba" 라면 아래와 같이 문자열의 앞과 뒤를 비교하며 회문여부를 판단한다.

 

[문자열_회문 그 1]

 

 

 

[문자열_회문 그 2]

 

 

 

[문자열_회문 그 3]

 

모든 문자의 앞 뒤가 같다면 회문이므로 0을 반환한다.

 

 

 

 

 

 

 

중간에 회문이 되지 않는 경우가 있는 문자열은 다음과 같이 결괏값을 구할 수 있다.

 

[문자열_유사회문 그 1]

 

 

 

[문자열_유사회문 그 2]

 

우선은 문자열의 앞과 뒤를 순차적으로 탐색하며 회문인지를 판단한다.

 

 

 

 

 

[문자열_유사회문 그 3]

 

 

 

[문자열_유사회문 그 4]

 

만약 앞과 뒤의 문자가 다른데, 문자를 지워서 회문이 될 수 있는 가능성이 있다면 해당 문자를 지우고 다시 탐색을 시작한다.

 

 

 

 

이 문자열의 경우는 앞의 문자를 지워도 되고 뒤의 문자를 지워도 되기 때문에 양쪽의 경우를 둘 다 구해야 한다.

 

[문자열_유사회문 그 5]

 

 

 

 

[문자열_유사회문 그 6]

 

 

 

 

[문자열_유사회문 그 7]

 

뒤의 문자를 지웠을 경우 회문이 되지 않는다.

이 경우 뒤의 문자를 지우는 경우는 탐색을 중단한다.

 

 

 

 

 

[문자열_유사회문 그 8]

 

우선 문자를 한번 지웠기 때문에 count + 1을 해준다.

여기에 문자를 지웠을 때, 결괏값의 최솟값을 count에 더해준다.

이 경우 앞 문자를 지웠을 때 회문이 되므로 문자를 지웠을 경우 반환 값은  0이 된다.

따라서 결괏값은 + 1 + 0 으로 1 => 유사회문이 된다. 

 

 

 

 

 

 

 

2.2 코드

2.2.1 checkPalindrome

[checkPalindrome]

//문자열 str이 회문인지 검사하는 메서드
private static int checkPalindrome(String str, int start, int end, int depth) {
    if (depth >= 2) {
        return 0;
    }
    
    int count = 0;
    //start, end가 가르키는 문자를 지웠을 때 결과값
    int deleteStartResult = 1;
    int deleteEndResult = 1;
    //문자를 하나 지웠는지를 판단하는 flag
    boolean deleteFlag = false;

    while (start < end) {
        if (str.charAt(start) == str.charAt(end)) {
            start++;
            end--;
            continue;
        }
        //start가 가르키는 문자를 지웠을 때 회문이 될 수 있는 경우
        //start의 문자를 지움 => start + 1 부터 검사
        //start + 1부터 end까지의 문자열이 회문인지 다시 검사해서 회문이 되지 않을 경우 1를 반환 받는다.
        if (start + 1 <= end && str.charAt(start + 1) == str.charAt(end)) {
            deleteFlag = true;
            deleteStartResult = checkPalindrome(str, start + 1, end, depth + 1);
        }
        //end가 가르키는 문자를 지웠을 때 회문이 될 수 있는 경우. 이하 동일
        if (end - 1 >= start && str.charAt(start) == str.charAt(end - 1)) {
            deleteFlag = true;
            deleteEndResult = checkPalindrome(str, start, end - 1, depth + 1);
        }

        //문자를 삭제 했다면 count를 늘려주고, start와 end를 지운 경우의 결과값에서 가장 최소가되는 결과값(최선의 경우)을 count에 더해준다.
        if (deleteFlag) {
            count++;
            count += Math.min(deleteStartResult, deleteEndResult);
        //유사회문도 될 수 없는 경우
        } else {
            count = 2;
        }
        break;
    }

    //count의 결과에 따라 return값 반환
    return count;
}

 

 

 

 

 

 

2.2.2 main

[main]

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int caseSize = scanner.nextInt();

    for (int i = 0; i < caseSize; i++) {
        String str = scanner.next();
        System.out.println(checkPalindrome(str, 0, str.length() - 1 ,0));
    }
}

 

 

 

 

 

 

 

 

 

 

3. 전체 코드

[전체 코드]

import java.util.Scanner;

public class 회문_17609 {

    //문자열 str이 회문인지 검사하는 메서드
    private static int checkPalindrome(String str, int start, int end, int depth) {
        if (depth >= 2) {
            return 1;
        }
        int count = 0;
        //start, end가 가르키는 문자를 지웠을 때 결과값
        int deleteStartResult = 1;
        int deleteEndResult = 1;
        //문자를 하나 지웠는지를 판단하는 flag
        boolean deleteFlag = false;

        while (start < end) {
            if (str.charAt(start) == str.charAt(end)) {
                start++;
                end--;
                continue;
            }
            //start가 가르키는 문자를 지웠을 때 회문이 될 수 있는 경우
            //start의 문자를 지움 => start + 1 부터 검사
            //start + 1부터 end까지의 문자열이 회문인지 다시 검사해서 회문이 되지 않을 경우 2를 반환 받는다.
            if (start + 1 <= end && str.charAt(start + 1) == str.charAt(end)) {
                deleteFlag = true;
                deleteStartResult = checkPalindrome(str, start + 1, end, depth + 1);
            }
            //end가 가르키는 문자를 지웠을 때 회문이 될 수 있는 경우. 이하 동일
            if (end - 1 >= start && str.charAt(start) == str.charAt(end - 1)) {
                deleteFlag = true;
                deleteEndResult = checkPalindrome(str, start, end - 1, depth + 1);
            }

            //문자를 삭제 했다면 count를 늘려주고, start와 end를 지운 경우의 결과값에서 가장 작은 결과값(최선의 경우)을 count에 더해준다.
            if (deleteFlag) {
                count++;
                count += Math.min(deleteStartResult, deleteEndResult);
            } else {
                count = 2;
            }
            break;
        }

        //count의 결과에 따라 return값 반환
        if (count >= 2) {
            return 2;
        } else if (count == 1) {
            return 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int caseSize = scanner.nextInt();

        for (int i = 0; i < caseSize; i++) {
            String str = scanner.next();
            System.out.println(checkPalindrome(str, 0, str.length() - 1 ,0));
        }
    }
}