[BaekJoon] 17609 회문 (Java)

1.  문제 링크

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

2.  문제

요약

• 회문 또는 팰린드롬은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말합니다.
• 유사 회문은 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열을 말합니다.
• 문자열이 주어졌을 때, 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 유사회문인지 판단하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 30보다 작거나 같은 정수인 문자열의 개수 T가 주어지고 두 번째 줄부터 T개의 줄에는 알파벳 소문자로만 이루어져 있고 문자열의 길이가 3 이상 100,000 이하인 문자열들이 주어집니다.
• 출력: 첫 번째 줄부터 T개의 줄에는 각 문자열이 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static String palindrome;
	
	static void input() {
		Reader scanner = new Reader();
		int test_num = scanner.nextInt();
		for(int i = 0; i < test_num; i++) {
			palindrome = scanner.nextLine();
			sb.append(isPalindrome(0, palindrome.length() - 1, 0)).append('\n');
		}
	}
	
	static int isPalindrome(int l, int r, int cnt) {
		if(cnt == 2)
			return 2;
		int result = cnt;
		while(l < r) {
			if(palindrome.charAt(l) != palindrome.charAt(r)) {
				int left = isPalindrome(l + 1, r, cnt + 1);
				int right = isPalindrome(l, r - 1, cnt + 1);
				result = Math.min(left, right);
				break;
			}
			l++;
			r--;
		}
		return result;
	}
	
	public static void main(String[] args) {
		input();
		System.out.println(sb.toString());
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			return str;
		}
	}
}

4.  접근

• 이 문제는 투포인터를 이용하여 구할 수 있는 문제입니다.
• 주어진 문자열들을 받고 각 문자열이 회문인지 유사 회문인지 둘 다 아닌지를 isPalindrome() 함수에서 판단합니다.
  • isPalindrome() 함수는 3개의 파라미터를 갖는데, l은 왼쪽 포인터의 인덱스, r은 오른쪽 포인터의 인덱스, cnt는 삭제한 문자의 개수 및 회문인지 유사 회문인지 둘 다 아닌지를 나타내는 파라미터입니다.
• 처음에 왼쪽 포인터는 0번 인덱스, 오른쪽 포인터는 문자열의 마지막 인덱스에서 시작합니다.
• 왼쪽 포인터가 오른쪽 포인터보다 크거나 같아지기 전까지 각 포인터를 하나씩 이동시키며 해당 위치의 두 문자가 서로 같은지 확인합니다.
  • 만약 두 문자가 서로 같다면 두 포인터를 한 칸씩 이동시킵니다.
  • 만약 두 문자가 서로 같지 않다면 왼쪽 포인터에 있는 문자를 하나 삭제하는 경우와 오른쪽 포인터에 있는 문자를 하나 삭제하는 경우 각각을 재귀함수 호출을 통해 진행합니다.
    • 왼쪽 포인터에서 문자를 하나 삭제하는 경우는 왼쪽 포인터 위치인 l에 1을 더하고 cnt에 1을 더하여 재귀함수를 호출합니다.
    • 오른쪽 포인터에서 문자를 하나 삭제하는 경우는 오른쪽 포인터 위치인 r에 1을 더하고 cnt에 1을 더하여 재귀함수를 호출합니다.
  • 재귀함수 호출을 진행하다 전달한 파라미터 cnt의 값이 2라면 왼쪽 포인터와 오른쪽 포인터에서 각 문자를 비교하다가 문자를 한 개를 삭제하였음에도 다른 문자가 한 번 더 나타났다는 의미가 되므로 이는 회문도 유사 회문도 될 수 없기 때문에 2를 반환합니다.
  • 왼쪽 포인터가 오른쪽의 포인터보다 크거나 같을 때까지 반복문이 모두 진행되어 반복문이 끝난 상황이라면 cnt에 따라 회문인지 유사 회문인지 판단할 수 있습니다.
    • 만약 반복문이 끝났을 때 cnt가 0이라면 문자를 한 개도 삭제하지 않고 양쪽 포인터의 각 문자가 반복문이 끝날 때까지 같았다는 의미가 되므로 이는 회문에 해당합니다. 그렇기 때문에 0을 반환합니다.
    • 만약 반복문이 끝났을 때 cnt가 1이라면 문자를 한 개 삭제하고 양쪽 포인터의 각 문자가 반복문이 끝날 때까지 같았다는 의미가 되므로 이는 유사 회문에 해당합니다. 그렇기 때문에 1을 반환합니다.
    • 위 경우들을 생각해보면 cnt가 곧 반환되는 숫자와 같기 때문에 cnt를 반환합니다.