백준 17609번 회문 파이썬

https://www.acmicpc.net/problem/17609

내 코드

def is_palindrome(s):
    return s == s[::-1]

def is_similary(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            temp1 = s[left+1:right+1]
            temp2 = s[left:right]
            return is_palindrome(temp1) or is_palindrome(temp2)
        left += 1
        right -= 1
    return False

T = int(input())

for i in range(T):
    s = input()
    
    if is_palindrome(s):
        print(0)
    elif is_similary(s):
        print(1)
    else:
        print(2)

---

Review

논리의 순서는 다음과 같이 생각했습니다.

팰린드롬인 경우(is_palindrome) -> 유사 팰린드롬인 경우(is_similary) -> 둘 다 아닌 경우

처음에는 아래와 같이 코드를 구현했습니다.

def is_palindrome(s):
    return s == s[::-1]

def is_similary(s):
    
    for i in range(len(s) - 1):
        temp = s[:i] + s[i+1:]
        
        if is_palindrome(temp):
            return True
        
    return False

T = int(input())

for i in range(T):
    s = input()
    
    if is_palindrome(s):
        print(0)
    elif is_similary(s):
        print(1)
    else:
        print(2)

 

해당하는 인덱스 기준으로 왼쪽 ( s[:i] ) , 오른쪽 ( s[i+1:] ) 나눠서 해당 index의 단어를 하나씩 빼서 팰린드롬인지 아닌지 판별하였습니다.

하지만 시간 복잡도는 위의 is_similary 함수를 봤을 때, 최악의 경우 O(N^2) 이 나옵니다. ( T는 최대 30 이라 생략 )

그래서 is_similary 함수를 투포인터 기법을 사용하여, 평균 복잡도를 줄였습니다. ⭐️⭐️

2개씩 비교하는 is_palindrome 함수가 작동됩니다.

def is_similary(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            temp1 = s[left+1:right+1]
            temp2 = s[left:right]
            return is_palindrome(temp1) or is_palindrome(temp2)
        left += 1
        right -= 1
    return False

평균 복잡도는 줄였지만, 최악의 경우 시간 복잡도는 여전히 O(N^2) 이 됩니다.
크게 시간 복잡도를 줄이진 않았지만 처음에 구현했던 코드보다는 반 정도, 최적화를 하였습니다.

바로 위의 is_similary(s) 함수의 의 작동방식을 예시 (s = "summuus") 로 하나 설명하고, 마무리하겠습니다.