[백준 17609번] 회문

예제 입력은 다 통과했으나 틀렸다고 하여서 반례를 찾게된게 

 

baaba 였다

 

출력으로 1이 나와야 하는데

 

나의 코드에서는 2가 나왔다.

 

처음의 알고리즘 설계를 왼쪽 오른쪽에서 하나씩 문자를 읽으면서 비교하다가

 

다른 문자가 나오면

 

left+1 이랑 right 랑 비교해서 같다면 left를 없애고 계속 진행

 

left 랑 right-1 랑 비교해서 같다면 right를 없애고 계속 진행

 

둘 다 안되면 일반 문자열로 판별 하도록 하였는데,

 

이런식으로 설계를 하니 left+1 이랑 right 도 같고 left 랑 right-1 도 같을 수 있기에 해당 경우에는

 

둘 다 진행을 해봐야 한다.

 

baaba로 설명을 해보면 

 

left (0번째 index) : b 

right (4번째 index) : a 

 

left와 right가 다른 문자이다.

 

그래서 left+1(a) 와 right(a)를 비교해보니 같다.

그래서 baaba에서 b를 제거한 aaba가 회문인지 계속해서 확인하지만 이는 일반 문자열이라고 판별된다.

 

하지만 left(b) 와 right-1(b) 도 같기에

baaba에서 a를 제거한 baab는 회문이기에 

baaba는 일반 문자열이 아닌 유사 회문으로 판별되어야한다.

 

그래서 결론적으로 나의 코드는 이러하다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		int count = scan.nextInt();
		
		String[] inputs = new String[count];
		for(int i = 0; i < count; i++) {
			inputs[i] = scan.next();
		}
		
		int[] results = new int[count];
		
		for(int i = 0; i < count; i++) {
			results[i] = isPalindrome(inputs[i]); 
		}
		
		for(int result : results) {
			System.out.println(result);
		}
		
		scan.close();
	}
	
	private static int isPalindrome(String word) {
		
		final int PALINDROM = 0;
		final int PSEUDO_PALINDROM = 1;
		final int NORMAL = 2;
		
		int result = PALINDROM;
		
		int left = 0;
		int right = word.length() - 1;
		
		while(left < right) {
			
			if(word.charAt(left) != word.charAt(right)) {
				if(left + 1 >= right) {
					result = PSEUDO_PALINDROM;
					break;
				}
				if((word.charAt(left + 1) == word.charAt(right)) && (word.charAt(left) == word.charAt(right - 1))) {
					result = Math.min(isPseudoPalindrom(word, left + 1, right), isPseudoPalindrom(word, left, right - 1));
				} else if(word.charAt(left + 1) == word.charAt(right)) {
					result = isPseudoPalindrom(word, left + 1, right);
				} else if(word.charAt(left) == word.charAt(right - 1)) {
					result = isPseudoPalindrom(word, left, right - 1);
				} else {
					result = NORMAL;
				}
				break;
			}
			
			left++;
			right--;
		}
		
		return result;
	}
	
	private static int isPseudoPalindrom(String word, int left, int right) {
		
		final int PSEUDO_PALINDROM = 1;
		final int NORMAL = 2;
		
		int result = PSEUDO_PALINDROM;
		
		while(left < right) {
			
			if(word.charAt(left) != word.charAt(right)) {
				result = NORMAL;
				break;
			}
			
			left++;
			right--;
		}
		
		return result;
	}
}

isPseudoPalindrom()을 추가해주어서,

left+1 와 right가 일치하면서 left 와 right-1가 일치하는 경우는

둘 다의 경우를 확인해주면서 해결하였다.