[백준[ 17609 회문 Python 풀이와 반례

첨엔 이게 왜 골드지? ㅎㅎ 이러면서 풀었는데

반례가 계속 나온다 ㅎㅎ..... 엉엉 원래는 투포인터로 풀었는데, 엄청 삽질을 했다 
그러다가 파이썬 배열 원소 뒤집는걸  word[::-1] 이런식으로 써도 시간초과가 안난다는걸 알게되었고, 다른 분 풀이 참고해서 끝냈다 

1. 우선 투포인터로 left, right 를 각각 0 과 len(word)-1 로 지정해주어서 맨 앞과 맨 뒤에서부터 하나씩 글자를 비교한다 
2. 글자가 같으면 단순하게 포인터를 left는 앞으로, right는 뒤로 한칸 움직이면 된다 
3. 글자가 다르면 left가 가리키는 글자을 제거하는 방법과 right가 현재 가리키는 글자를 제거하는 방법이 있다 -> 난 여기서 삽질을 엄청 했다 
직접 해보면 된다 ㅎ

우선, 인덱스 크기가 left는 항상 right 보다 작아야 하므로 조건을 명시한다 
그리고 left 가 가리키는 글자를 제거한다고 생각하고 배열의 슬라이싱을 word[:left] + word[left+1:] 로 만든다 
그리고 이어 붙인 temp 문자열을 뒤집었을 때와 비교한다 
temp[:] == temp[::-1] 가 True이면 유사회문이다 하나만 삭제해주면 펠린드롬이 되기 때문

right 도 동일하게 확인한다. word[:right] + word[right+1:] 로 temp를 만들고 문자열 뒤집었을 때와 비교한다 

그리고 두 가지 경우에 해당되지 않으면, 일반 문자열에 해당한다. 

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

17609번: 회문

 

n = int(input())

def solve(left, right):
    while left <= right:
        if word[left] == word[right]:
            left += 1
            right -= 1
        else:
            # 오른쪽 문자열 제거
            if left < right -1: # 인덱스 확인하기
                temp = word[:right] + word[right+1:]
                if temp[:] == temp[::-1]:
                    return 1
            # 왼쪽 문자열 제거
            if left + 1 < right:
                temp = word[:left] + word[left+1:]
                if temp[:] == temp[::-1]:
                    return 1
            return 2
    return 0

for _ in range(n):
    word = input()
    left = 0
    right = len(word) - 1
    print(solve(left, right))

그리고 아래는 백준 Q&A 게시판을 참고하여 얻어낸 반례 모음이다 
[입력]
21
abbab
aab
aaab
aaaab
aaaaab
aaaaaab
axaaxaa
abcddadca
aabcbcaa
ababbabaa
abca
babba
sumumuus
XYXYAAYXY
abc
cccfccfcc
abcddcdba
ppbpppb
aabcdeddcba
aabab
aapqbcbqpqaa

[출력]
1
1
1
1
1
1
1
2
1
1
1
1
1
1
2
1
1
2
2
2
1

17609번: 회문