BOJ 17609 - 회문

풀이

---

앞뒤가 똑같은 문자열을 회문이라고 하는데 한글자를 제외했을 때 회문을 만들어 내는 문자열을 유사회문이라고 한다.

이때 주어진 문자열이 회문인지, 유사회문인지, 그 외인지를 판단하는 알고리즘을 짜야한다.

처음에는 리스트 슬라이싱을 통해 각 자리수를 제외하여 새로운 문자열을 만들어낸 후 비교해보는 방식을 선택했었다.

하지만 문자열 최대길이가 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))

References

---

• BOJ 17609 - 회문