[백준] 17609. 회문 (파이썬)

 

 

 

🗂️   문제 

17609. 회문

---

---

📌   Point

Two Pointer

 

• 문자열이 회문인지 확인하기 위해서는 문자열이 대칭인지를 확인해야 한다.
• 대칭인지를 확인하기 위해 첫 번째 문자와 마지막 문자에 각각 포인터를 두고 중간 문자까지 각 포인터가 가리키는 문자가 같은지 확인한다.

 

https://youngone-kang.tistory.com/30

[Algorithm] Two Pointers (투 포인터)

 

 

 

 

 

---

📄   코드

def main():
    T = int(input())
    
    # 문자열이 회문인지 판별하는 함수
    def is_palindrome(word):
        l, r = 0, len(word) - 1
        while l < r:
            if word[l] == word[r]:
                l += 1
                r -= 1
            else:
                # 왼쪽 문자 제거 후 회문인지 확인
                if is_palindrome_after_removal(word, l + 1, r):
                    return 1 # 유사 회문
                # 오른쪽 문자 제거 후 회문인지 확인
                if is_palindrome_after_removal(word, l, r - 1):
                    return 1 # 유사 회문
                return 2 # 회문 아님
        return 0 # 회문
    
    # 한 글자를 제거한 후 회문인지 확인하는 함수
    def is_palindrome_after_removal(word, left, right):
        while left < right:
            if word[left] != word[right]:
                return False
            left += 1
            right -= 1
        return True
    
    for _ in range(T):
        word = input()
        result = is_palindrome(word)
        print(result)

if __name__ == "__main__":
    main()

---

✍🏻   풀이

시간 복잡도 : O(n)

 

 

1.  팰린드롬 판별 함수

입력 문자열이 다음 세 가지 중 어디에 해당하는지 판별한다.

• 0  :  팰린드롬
• 1   :  한 글자 삭제하면 팰린드롬이 되는 유사 팰린드롬
• 2  :  팰린드롬 X

투 포인터 방식으로 팰린드롬 판별

 

• l, r = 0, len(word)-1로 초기화
  • 왼쪽(l), 오른쪽(r)에서 시작하여 l += 1, r -= 1로 값을 갱신하며 가운데로 이동하면서 비교한다.
• while l < r 루프
  • 각 포인터의 문자가 같으면 l은 오른쪽으로 r은 왼쪽으로 이동한다.
  • 문자가 다르면 다음 두 경우를 확인한다.
    1. 왼쪽 문자(word[l])를 제거하면 팰린드롬이 되는지
    2. 오른쪽 문자(word[r])를 제거하면 팰린드롬이 되는지
  • 이를 확인하고자 유사 팰린드롬 확인 함수를 생성한다.

2.  유사 팰린드롬 확인 함수

• 입력받은 word[left : right + 1] 부분 문자열이 팰린드롬인지 확인한다.
• while l < r 루프를 돌면서 두 문자가 다르면 False를 반환하고, 끝까지 비교하면서 모든 문자가 같으면 True를 반환한다.