[백준] 17609 회문 python

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

17609번: 회문

회문 체크하는게 굉장히 오래걸렸다.

처음 시도는 슬라이싱으로 했으나 시간초과가 되어 인덱스로 접근하는 방식으로 했다.

 

# import sys; input = sys.stdin.readline
def check_palindrome(string, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(string) - 1

    cnt = 0
    pre_idx, post_idx = start, end
    while pre_idx <= end and post_idx >= start:
        if pre_idx == (start + end + 1) // 2 \
                or post_idx == end - ((start + end + 1) // 2):
            if string[pre_idx] != string[post_idx]:
                cnt += 1
            break
        if cnt > 1:
            break

        if string[pre_idx] == string[post_idx]:
            pre_idx += 1
            post_idx -= 1
            continue

        cnt += 1
        if string[pre_idx + 1] == string[post_idx] and string[pre_idx] == string[post_idx - 1]:
            tmp1 = check_palindrome(string, pre_idx + 1, post_idx)
            tmp2 = check_palindrome(string, pre_idx, post_idx - 1)
            if not tmp1 or not tmp2:
                break
            else:
                continue

        elif string[pre_idx + 1] == string[post_idx]:
            pre_idx += 1
        elif string[pre_idx] == string[post_idx - 1]:
            post_idx -= 1
        else:
            return 2

    return cnt

def main():
    answer = []
    for _ in range(int(input())):
        answer.append(check_palindrome(input().rstrip()))
    print(*answer, sep='\n')


if __name__ == "__main__":
    main()

---

슬라이싱으로 풀었는데 조금더 빠른 코드가 있어서 가져왔다

import sys; input = sys.stdin.readline

def is_palindrome(s):
    middle = len(s) // 2 + 1
    if s[:middle] == s[-middle:][::-1]:
        return True
    return False


def like_palindrome(s):
    for i in range(len(s) // 2):
        if s[i] != s[(len(s) - 1) - i]:
            if is_palindrome(s[:i] + s[i + 1:]) \
                    or is_palindrome(s[:len(s) - 1 - i] + s[len(s) - i:]):
                return True
            else:
                return False


def main():
    T = int(input())
    strings = [input().rstrip() for _ in range(T)]
    answer = []
    for s in strings:
        if is_palindrome(s):
            answer.append(0)
        elif like_palindrome(s):
            answer.append(1)
        else:
            answer.append(2)
    print(*answer, sep='\n')


if __name__ == "__main__":
    main()

 

python3에선 슬라이싱이 빨랐고, pypy3에선 인덱싱이 더 빨랐다.