[백준] S1 17609번 회문 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

17609번: 회문

[문제] 

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

[입력]

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

[출력]

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

 

 

---

[풀이]

1. 문자열을 입력받아준다.

2. 입력받은 문자열을 처음과 맨 끝에서부터 탐색을 한다.

3. 같다면 왼쪽을 감소시키고, 오른쪽을 증가시키면서 탐색한다.

4. 만약 다른 경우가 발생하면 왼쪽을 1칸 증가하고 탐색하고, 오른쪽을 1칸 감소하고 탐색한다.

5. 다른 경우가 발생하면 count를 증가시켜준다.

6. 카운트가 0이라면 0, 1이라면 1 or 2라면 1, 3이라면 2를 출력해준다.

[접근]

1. 투 포인터로 탐색을 하는 것을 생각하였다.

2. 탐색을 하면서 다른 문자가 나왔을 때를 어떻게 처리해야 할지 고민했다.

3. 다른 문자가 나올 경우, 왼쪽을 제거하고 탐색하는 경우와, 오른쪽을 탐색하는 경우가 발생할 수 있으니 이 두 경우를 다 탐색해준다.

4. 탐색 후 count가 2보다 큰 경우 -1을 해준다.

[코드]

package BOJ_silver;

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

public class Main_S1_17609 {
	static int T; // 단어의 수
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		// 초기화
		String word = "";
		int result = 0;
		
		for(int i = 0; i < T; i++) {
			word = br.readLine();
			
			result = check(word);
			
			// 다른게 없다면 0으로 넘어온다.
			// 하지만 다른게 발생을 하면 1씩 추가로 증가된다.
			// 그래서 -1을 해준다.
			if (result >= 2)
				System.out.println(result - 1);
			else
				System.out.println(result);
		}
	}
	
	public static int check(String word) {
		int result = 0;
		int left = 0;
		int right = word.length()-1;
		
		while(left <= right) {
			// 왼쪽 포인터와 오른쪽 포인터 체크
			// 같으면
			if(word.charAt(left) == word.charAt(right)) {
				left++; // 왼쪽은 증가
				right--; // 오른쪽은 감소
			}
			else { // 다르면
				result = 1; // 위에서 처리 안되고 내려오면 최소 1번은 다르니까
				
				int l = left + 1; // 임시 왼쪽 포인터
				int r = right; // 임시 오른쪽 포인터
				
				// 왼쪽을 이동해서 체크 (왼쪽을 1개 지웠다고 생각)
				while(l <= r) {
					if(word.charAt(l) == word.charAt(r)) {
						l++;
						r--;
					}
					else {
						result++; // 다르면 증가
						break;
					}
				}
				
				l = left;
				r = right - 1;
				
				// 오른쪽을 이동해서 체크 (오른쪽을 1개 지웠다고 생각)
				while(l <= r){
					if(word.charAt(l) == word.charAt(r)) {
						l++;
						r--;
					}
					else {
						result++; // 다르면 증가
						break;
					}
				}
				
				return result; // 왼쪽 or 오른쪽 중 1개만 다르다면 2, 둘 다 다르면 3
			}
		}
		
		return result; // 다른게 없다면 0
	}
}