[SWEA] 4579. 세상의 모든 팰린드롬 2

문제

어떤 단어를 뒤에서 앞으로 거꾸로 썼을 때 원래의 단어와 같으면 이를 팰린드롬이라고 한다.

예를 들어 “madam”은 뒤에서 앞으로 읽어도 “madam”이기 때문에 팰린드롬이다. 그러나 “dog”는 뒤에서 앞으로 읽으면 “god”이기 때문에 팰린드롬이 아니다.

“doggod”은 뒤에서 앞으로 읽으면 “doggod”이므로 팰린드롬이다.

25XX년 의석이는 알파벳 소문자로 만든 단어들 중에서 팰린드롬인 것들을 모두 모아(그 단어에 뜻이 있건 없건) 데이터베이스에 넣었다.

요즘은 저장 장치가 발달해서 매우 많은 팰린드롬을 저장할 수 있기 때문에 모든 팰린드롬을 저장하지 못할 것이라는 걱정은 하지 않아도 좋다.

의석이는 이 데이터베이스에서 특정한 패턴에 매치되는 팰린드롬을 찾으려고 한다.

의석이는 알파벳 소문자와 ‘*’를 사용한 패턴과 매치되는 단어를 찾는 명령을 내릴 수 있는데, ‘*’는 길이가 0 이상인 임의의 알파벳들로 대체될 수 있는 와일드 카드이다.

예를 들어 의석이가 “a*a”에 매치되는 단어를 찾으라는 명령을 내리면, “aa”, “ana”, “appa”등의 팰린드롬을 데이터베이스에서 찾을 수 있을 것이다.

“asia”는 이런 패턴에 매치되기는 하지만 팰린드롬이 아니기 때문에 데이터베이스에서 발견되지 않을 것이고, “aab”는 패턴에 매치되지 않기 때문에 찾아주지 않을 것이다.

주어진 패턴과 매치되는 단어가 데이터베이스에 하나라도 있는지 아닌지 출력하는 프로그램을 작성하라.

 

풀이방법

'*'에는 길이가 0 이상인 임의의 알파벳으로 대체될 수 있다.

 

예를 들어 ca*bcdac라는 입력이 주어졌다면

 

'*'는 'dcb'로 대체될 수 있으므로 cadcbbcdac가 되어 팰린드롬이 된다.

 

패턴을 살펴보면 ca*bcdac에서 '*'은 ca*bcdac 빨간색 문자들까지 대체가능하다.

 

ca*bcdac에서 '*'이 나오기 이전 문자(파란색 부분)만 앞 뒤가 같으면 나머지 부분은 대체가능하다.

 

즉, n개의 문자가 입력주어졌을 때 '*'이 i번째에 나왔다면

 

ca*bcdac

 

ca*bcdac

 

1부터 i-1번째 문자와 n부터 n-(i-1)번 째 글자가 각각 같다면 팰린드롬이 된다.

 

소스코드

package samsung;

import java.util.*;

public class s_4579 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			String s = sc.next();
			int flag = 0;
			for(int i = 0 ; i < s.length()/2; i++) {
				if(s.charAt(i) == '*' || s.charAt(s.length() - 1 - i) == '*')
					break;
				if(s.charAt(i) != s.charAt(s.length() - 1 - i)) {
					flag = 1;
					break;
				}
			}
			if(flag == 0)
				System.out.println("#" + t + " Exist");
			else
				System.out.println("#" + t + " Not exist");
		}
	}
}