SW Expert Academy // 4522

SW Expert Academy 4522번 "세상의 모든 팰린드롬" 문제입니다.

TC = int(input())
for tc in range(1, TC+1):
  S = input()
  pell = True
  if len(S) == 1:
    pell = True
  else:
    for i in range(0, len(S)//2):
      if S[i] != S[len(S)-1-i]:
        if S[i] != '?' and S[len(S)-1-i] != '?':
          pell = False
          break

  if pell:
    print("#%d Exist"%tc)
  else:
    print("#%d Not exist"%tc)

펠린드롬, 회문이란 제대로 읽었을 경우와 거꾸로 읽었을 경우 똑같은 문자열을 말한다.

 

예를 들어 dog는 거꾸로 읽으면 god이므로 기존의 단어와 일치하지 않아 펠린드롬이 아니다.

 

반대로 madam은 거꾸로 읽어도 madam이기 때문에 기존의 단어와 일치하므로 펠린드롬이다.

 

하지만 이 문제는 단순히 펠린드롬인지 아닌지를 판별하는 것이 아니라 와일드카드 '?' 문자의 존재가 있다.

 

'?' 역할은 '?' 자리에 아무 문자나 들어올 수 있다는 뜻이다.

 

예를 들어 as?a는 '?'자리에 아무 문자나 들어가서 as?a가 펠린드롬이 된다면 펠린드롬이 맞다고 정의하는 것이다.

 

as?a에서 '?'자리에 's'가 들어가면 assa로 펠린드롬이 되므로 as?a는 펠린드롬이 존재한다.

 

반대로 as?ba는 '?'자리에 어느 문자가 들어가도 펠린드롬이 되지 않으므로 as?ba는 펠린드롬이 존재하지 않는다.

 

나의 펠린드롬 문제를 푸는 방식은 펠린드롬 bool 변수를 만들어서 True(펠린드롬이다)로 초기화한다.

 

그리고 문자열의 맨 앞과 맨 뒤부터 점차 안쪽으로 두 개씩 비교한다.

 

만약 다른 문자가 나왔을 경우 펠린드롬 bool 변수를 False(펠린드롬이 아니다)로 재할당하고 펠린드롬 검사 반복문을 빠져나온다.

 

그리고 이 문제에서는 다를 경우에도 두 문자 중 어느 것도 '?'가 아니면 다른 경우이므로 펠린드롬 bool 변수를 바꾸고 만약 '?'가 둘 중 하나라도 존재하면 펠린드롬 bool 변수를 바꾸지 않는다.