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

문제

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

예를 들어 “madam”은 뒤에서 앞으로 읽어도 “madam”이기 때문에 팰린드롬이다.

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

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

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

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

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

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

예를 들어 경근이가 “a??a”에 매치되는 단어를 찾으라는 명령을 내리면, “assa”, “appa”등의 팰린드롬을 찾아 줄 것이다.

“asia”는 이런 패턴에 매치되기는 하지만 팰린드롬이 아니기 때문에 찾아주지 않을 것이고, “aa”, “aab”, “ana”, “aaaaa”는 패턴에 매치되지 않기 때문에 찾아주지 않을 것이다.

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

 

풀이방법

회문 문제와 같지만 한 한가지 조건이 더 붙는다.

 

일반적인 회문 문제는 단어를 반으로 나누어 i번째 문자와 n-i번째 문자가 같은지 확인하는 문제이다.

 

이 문제 같은 경우는 회문처럼 두 문자를 비교하되, i또는 n-i번째 문자가 '?'일 경우, 두 문자가 같은 것으로 취급해준다.

 

소스코드

package samsung;

import java.util.*;

public class s_4522 {
	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 n = s.length();
			int flag = 0;
			for(int i = 0; i < n/2; i++) {
				if((s.charAt(i) == '?') || (s.charAt(n-1-i) == '?'))
					continue;
				if(s.charAt(i) != s.charAt(n-i-1)) {
					flag = 1;
					break;
				}
			}
			System.out.print("#" + t + " ");
			if(flag == 1)
				System.out.println("Not exist");
			else
				System.out.println("Exist");
		}
	}
}