[BOJ] 17609번 - 회문 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

이 문제는 회문을 알아내는 것이다.

단, 1개를 제거하면 회문이 되는 것도 알아내야 한다. 이 부분에서 반례를 확인하고 고치는 과정을 정리한다.

 

회문의 특성으로 가운데를 기점으로 양쪽이 같아야 하므로 start, end를 두어 비교했다.

처음에 내가 회문인지 알아내는 함수를 작성한 코드는 아래와 같다.

public static int isPalindrome(String s) {
    int start = 0;
    int end = s.length() - 1;

    int count = 0;
    while(start <= end) {
        if(s.charAt(start) == s.charAt(end)) {
            start++;
            end--;
        }
        else {
            count++;
            if(s.charAt(start+1) == s.charAt(end)) {
                start++;
            }
            else if(s.charAt(start) == s.charAt(end-1)) {
                end--;
            }
            else {
                count++;
            }
        }
        if(count > 1) {
            break;
        }
    }
    if(count > 1) {
        return 2;
    }
    return count;
}

 

그냥 단순하게 생각하여 start와 end 위치에 있는 문자가 같지 않을 때 각각 다음 문자를 확인했다.

그러나 반례가 있다.

1
xyyyyxy

 

위와 같은 입력이 주어졌을 경우 정답은 1이다.

하지만 내 코드는 2가 나온다.

왜냐하면 뒤의 y를 제거하는 것이 아니라 앞의 x를 제거했기 때문이다.

1
yxyyyyx

 

반대로 위와 같은 경우는 올바르게 1이 출력되었다.

즉, 현재 구현된 코드로는 앞부분의 문자를 제거해야지만 올바른 값을 찾을 수 있다.

 

그래서 생각한 방식은 간단하다.

전체 문자열에서 다른 부분을 찾고 그 다른 부분안의 문자열이 회문일 경우에는 유사회문이다.

1. start와 end 의 문자가 다를 때까지 반복하여 다른 부분 찾기
2. 만약 다르지 않다면 회문이다.
3. 다른 부분이 있다면
   1. 이미 한번 제거했을 경우이면 회문이 아니다.
   2. 앞의 문자를 제거해 start + 1 ~ end 까지의 문자열이 회문인지 확인
   3. 뒤의 문자를 제거해 start ~ end - 1 까지의 문자열이 회문인지 확인
   4. 둘 중 하나라도 0이 반환되는 회문이면 유사회문이다.
   5. 아니면 회문이 아니다.

---

🍀 풀이 🍀

package Baekjoon;

import java.io.*;

public class String17609 {
    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++) {
            String s = br.readLine();
            bw.write(isPalindrome(s, 0, s.length()-1, false) + "\n");
        }
        bw.flush();
        bw.close();
    }

    /**
     * 팰린드롬 문자열인지 확인하는 함수
     * @param s 문자열
     * @param start 현재 탐색하고 있는 앞 인덱스
     * @param end 현재 탐색하고 있는 뒤 인덱스
     * @param remove 유사회문인지 구분하는 변수
     * @return 회문 0, 유사회문 1, 아닌 경우 2
     */
    public static int isPalindrome(String s, int start, int end, boolean remove) {
        boolean flag = false;
        while(start <= end) {
            if(s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            }
            else {
                flag = true;
                break;
            }
        }

        if(flag) {
            if (remove) {
                return 2;
            }
            int front = isPalindrome(s, start+1, end, true);
            int back = isPalindrome(s, start, end-1, true);
            if(front == 0 || back == 0) {
                return 1;
            }
            return 2;
        }
        return 0;
    }
}