[Baekjoon] 17609_회문

Gold V

문제(출처: https://www.acmicpc.net/problem/17609)

---

< 회문 >

 

문제 풀이 

 

문자열의 맨 처음과 끝을 시작으로 중간까지 보면서 회문인지 확인한다. 

 

* 왼쪽 문자를 제거했을 때, 오른쪽 문자를 제거했을 때 둘 다 회문일 가능성이 있다면 두 가지 경우 다 확인해야 한다.

 

 

 my solution (Java)

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

public class _17609_ { // 회문
	static String str;
	static boolean remove, check, result;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int t = Integer.parseInt(bf.readLine());

		for (int i = 0; i < t; i++) {
			str = bf.readLine();

			int start = 0, end = str.length() - 1;
			remove = false;
			check = false;
			result = false;

			check(start, end);

			if (check) {
				bw.write("2\n");
			} else if (remove) {
				bw.write("1\n");
			} else if (result) {
				bw.write("0\n");
			}
		}
		bw.flush();
	}

	private static void check(int start, int end) {
		while (start != end) {
			if (result) {
				break;
			}
			if (str.charAt(start) == str.charAt(end)) {
				if (start + 1 > end - 1 || start + 1 == end - 1) {
					result = true;
					break;
				}
				start++;
				end--;
			} else if (!remove) {
				if (str.charAt(start + 1) == str.charAt(end) && str.charAt(start) == str.charAt(end - 1)) {
					remove = true;
					if (start + 1 == end) {
						break;
					}
					check(start + 1, end);
					if (check) {
						check = false;
					}
					check(start, end - 1);
				}
				if (str.charAt(start) == str.charAt(end - 1)) {
					remove = true;
					start++;
					end -= 2;
				} else if (str.charAt(start + 1) == str.charAt(end)) {
					remove = true;
					start += 2;
					end--;
				} else {
					check = true;
					break;
				}
			} else {
				check = true;
			}
			if (result) {
				break;
			}
			if (check) {
				break;
			}
		}
	}
}

변수)
t : 문자열의 개수
str : 문자열
start, end : 인덱스
remove : 한 문자 삭제 여부
check : 회문, 유사회문 아닌 여부
result : 회문 여부

 

문자열의 개수만큼 문자열을 입력받아 회문인지 판단하기 위해 check 함수를 호출한다.

 

만약 문자열의 start 인덱스 위치의 문자와 end 인덱스 위치의 문자가 같다면 다음 문자를 확인하기 위해 start+1, end-1을 한다. 만약 stat 인덱스 위치의 문자와 end 인덱스 위치의 문자가 같지 않다면 한 문자를 삭제해서 회문을 만들 수 있는지 확인한다. 아직 한 문자를 삭제하지 않았다면 왼쪽 문자를 삭제했을 때와 오른쪽 문자를 삭제했을 때 어느 쪽이 회문일지를 판단해야 한다. 만약 왼쪽 문자를 지워도 오른쪽 문자와 같고, 오른쪽 문자를 지워도 왼쪽 문자와 같다면 왼쪽을 지웠을 때, 오른쪽을 지웠을 때 둘 다 확인해야 하므로 check 함수를 각각 호출한다. 하지만 이 경우가 아니라면 한쪽만 지운다. 모든 경우에 해당하지 않는다면 회문과 유사 회문이 아니므로 check를 true로 바꾸고 종료한다. 중간까지 확인해서 회문이 맞다면 result를 true로 바꾸고 종료한다.

 

check가 true라면 회문과 유사회문이 아니므로 2를 출력하고 remove가 true라면 유사회문이므로 1을 출력, result가 true라면 0을 출력한다.

---

---