풀이
앞뒤가 똑같은 문자열을 회문이라고 하는데 한글자를 제외했을 때 회문을 만들어 내는 문자열을 유사회문이라고 한다.
이때 주어진 문자열이 회문인지, 유사회문인지, 그 외인지를 판단하는 알고리즘을 짜야한다.
처음에는 리스트 슬라이싱을 통해 각 자리수를 제외하여 새로운 문자열을 만들어낸 후 비교해보는 방식을 선택했었다.
하지만 문자열 최대길이가 100,000 이다 보니 역시나 시간초과가 일어났다.
그래서 선택한 것이 대칭위치의 문자를 각각 비교하다가 다른 문자열이 나왔을 경우 맨 앞 혹은 맨 끝 문자를 제외한 채로 비교해보는 것이다.
예시를 들어보자
”summuus” 라는 문자열이 있다.
01234567
summuus
0 과 7 은 s 로 같다.
1 과 6 은 u 로 같다.
2 와 5 는 m, u 로 다르다.
이때 “mmu” 를 만들어 0번째 자리나 2번째 자리를 제외하여 비교한다.
이 경우 2번째 자리인 “u” 를 제외하면 “mm” 이 되기 때문에 유사회문이라는 것을 알 수 있다.
위에 설명된 논리를 isFalse 함수를 통해 lFalse 와 rFalse 값을 받아낸 후 출력값에 맞춰 출력해주면된다.
소스코드
# 회문
import sys
input = sys.stdin.readline
def isFalse(s, l, r):
while l < r:
if s[l] == s[r]:
l += 1
r -= 1
else:
return False
return True
def isPalin(s, l, r):
while l < r:
if s[l] == s[r]:
l += 1
r -= 1
else:
lFalse = isFalse(s, l+1, r)
rFalse = isFalse(s, l, r-1)
if lFalse or rFalse:
return 1
else:
return 2
return 0
t = int(input())
for _ in range(t):
s = input().rstrip()
l, r = 0, len(s)-1
print(isPalin(s, l, r))