[백준_17609번] 회문

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

17609번: 회문

[문제]

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

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_17609 {
	static String str;
	static char[] arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		
		for(int i=0;i<t;i++) {
			str=sc.next();
			arr=str.toCharArray();
			
			// 팰린드롬일 경우 나머지 조검 검사하지 않고 0 출력후 다음 문장 탐색
			if(isPalindrome(0,str.length()-1)) {
				System.out.println(0);
				continue;
			}
			
			// 팰린드롬이 아니라면 유사회문인지 아닌지 탐색
			if(pseudo_palindrome(0,str.length()-1))
				System.out.println(1);
			else 
				System.out.println(2);
		}
	}
	
	// 투포인터를 사용하여 팰린드롬인지 확인하는 함수
	static boolean isPalindrome(int left, int right) {
		while(left<=right) {
			if(arr[left]!=arr[right]) // 대칭되는 알파벳이 같지 않다면 false return 
				return false;
			
			// 다음 알파벳 검사
			left+=1; 
			right-=1;
		}
		return true;
	}
	
	// 투포인터를 사용하여 유사회문인지 확인하는 함수
	static boolean pseudo_palindrome(int left, int right) {
		while(left<=right) {
			if(arr[left]!=arr[right]) { // 대칭되는 알파벳이 같지 않다면 
				// 대칭되지 않은 숫자들을 각각 제외해보고 팰린드롬인지 확인
				boolean new_left=isPalindrome(left+1,right);
				boolean new_right=isPalindrome(left,right-1);
				
				if(!new_left&&!new_right) // 둘다 만족하지 못한다면 false return
					return false;
				else 
					return true;
			}
			
			// 다음 알파벳 검사
			left+=1;
			right-=1;
		}
		
		return true;
	}
}

 

[고찰]

 이번 문제는 시간초과 문제로 인해 어떤 알고리즘을 선택하느냐가 중요한 문제였다. 해결 방법이 잘 떠오르지 않아 다른 사람의 포스팅을 보며 아이디어를 얻었다. 결론적으로 이번 문제를 해결하기 위해서는 투포인터를 사용해야 했다. 투포인터 문제는 1문제밖에 풀어보지 않아 이번 문제를 통해 좀더 유형에 익숙해지는 연습을 한것 같다. 

 문자열의 왼쪽 부터 탐색하는 left 변수와 오른쪽부터 탐색하는 right 변수를 두고 회문인지 검사하는 경우는 같지 않은 순간 바로 false를 return 한다. 유사회문인지 검사하는 경우는 left와 right가 같지 않은 경우 각각의 알파벳을 제외해보고 회문인지 검사하는 함수를 사용하여 둘 중에 회문인 경우가 나오면 true를 return하면 된다. 알고리즘만 알고나면 어렵지 않게 해결할 수 있어 투포인터를 연습하는데 딱인 문제인것 같다.