[BOJ/JAVA] 17609번: 회문

17609번: 회문

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

키워드

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열

회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)

문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력

---

구현

1. 문자열이 회문인지 판단하는 알고리즘

2. 문자열이 유사회문인지 판단하는 알고리즘

3. 그 외는 둘 다 아님 → 2출력

유사회문인지 판단하는 알고리즘

문자 하나를 삭제해서 회문이 되는지 판단하기 위해 2개의 포인터를 사용한다.

1. firstIndex: 문자열 맨앞에서 중앙까지 가는 포인터

2. lastIndex: 문자열 맨뒤에서 중앙까지 가는 포인터

• 두 포인터가 가리키는 문자가 같은 경우
  • firstIndex를 증가시킨다.
  • lastIndex를 증가시킨다.

• 두 포인터가 가리키는 문자가 다른 경우
  • 이미 문자를 지운 적이 있는 경우
    • 2 반환
  • 다음 2가지를 분기로 나누어 처리한다.
  • 왼쪽을 지우는 경우
  • 오른쪽을 지우는 경우

---

코드

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

public class java_17609 {
    static int T;

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

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

        while (T-- > 0) {
            String word = br.readLine();

            int result = checkPalindrome(word, 0, word.length() - 1, false);

            System.out.println(result);
        }

        br.close();

    }

    // 입력 문자열이 회문인지, 유사회문인지 판단하는 메소드
    // word, firstIndex, lastIndex, isDeleted
    private static int checkPalindrome(String word, int firstIndex, int lastIndex, boolean isDeleted) {
        // 모든 문자열을 비교했다면.. 종료
        // 유사회문, 회문 판단 처리
        if (lastIndex <= firstIndex) {
            return isDeleted ? 1 : 0;
        }

        // 현재 위치를 비교
        char firstChar = word.charAt(firstIndex);
        char lastChar = word.charAt(lastIndex);

        // 두 문자가 같은 경우
        if (firstChar == lastChar) {
            return checkPalindrome(word, firstIndex + 1, lastIndex - 1, isDeleted);
        }

        // 이미 지운적이 있는 경우 -> 회문, 유사회문이 아님
        if (isDeleted) {
            return 2;
        }

        // 두 문자가 다른 경우
        // 지운적이 없다면..firstChar 또는 lastChar을 지우자
        return Math.min(checkPalindrome(word, firstIndex + 1, lastIndex, true),
                checkPalindrome(word, firstIndex, lastIndex - 1,
                        true));
    }
}

---

Uploaded by N2T