[Python] BOJ / 17609번 / 회문

17609번: 회문

---

📝 풀이

• 문자열이 주어졌을 때 회문인지, 유사 회문인지, 일반 문자열인지 구분하여 출력하는 프로그램
• 문자열의 처음(left = 0)과 끝(right = len(word) - 1)에 포인터를 두고 대치되는 위치의 두 문자를 비교해 감
  • 1. 대치되는 두 문자가 동일한 경우 왼쪽 포인터(left)는 +1을, 오른쪽 포인터(right)는 -1을 하여 다음 문자 비교
  • 2. 대치되는 두 문자가 동일하지 않은 경우 왼쪽 문자 혹은 오른쪽 문자를 제거했을 때 회문이 되는지 확인
    • 이 과정에서 회문이 된다면 유사 회문이므로 '1'을 출력
    • 회문이 되지 않는다면 일반 문자열이므로 '2'를 출력
  • 3. 특별한 일 없이 포인터를 이동해가며 끝내 while문을 빠져나왔다면 문자열 그대로 회문인 경우이므로 '0'을 출력

---

💻 소스코드

import sys

input = sys.stdin.readline

def is_palindrome():
    left, right = 0, len(word) - 1

    while left < right:
        # 대치되는 두 문자가 동일한 경우
        if word[left] == word[right]:
            left += 1
            right -= 1
        else:
            if left + 1 < right:    # 왼쪽 문자 제거 후 회문 확인
                tmp = word[:left] + word[left + 1:]
                if tmp[:] == tmp[::-1]:
                    return 1
            if left < right - 1:    # 오른쪽 문자 제거 후 회문 확인
                tmp = word[:right] + word[right + 1:]
                if tmp[:] == tmp[::-1]:
                    return 1

            # 대치되는 두 문자가 동일하지 않으며, 문자 제거 후에도 회문이 되지 않는 경우
            return 2
    
    # 문자열 그대로 회문일 경우
    return 0

for _ in range(int(input())):
    word = list(input().rstrip())
    print(is_palindrome())