[백준] Python - 17609 회문

문제 링크

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

17609번: 회문

 

문제 풀이

이 문제는 회문(팰린드롬(palindrome))인지 혹은 유사회문인지 아닌지를 판단하는 문제였다. 그래서 나는 입력받은 문장에 대해서 제일 처음과 끝을 가리키는 포인터를 두 개 두고, 문장의 가운데로 좁혀가면서 확인하는 방법을 사용했다. 이 때, 주의할 점은! 앞 문자와 뒷 문자가 다를 경우에, 앞 문자 제거 후 회문인지/ 뒷 문자 제거 후 회문인지에 대한 검사를 두 번 다 해야한다. 왜냐하면 아직은 어디의 문자를 지워야 회문이 되는지 모르기 때문이다. 

 

1. 앞 문자 == 뒷 문자 : 포인터를 한 칸씩 이동
2. 앞 문자 != 뒷 문자 : 
   1. 뒷 문자 제거하고, 나머지 문장이 회문인지 확인
   2. 앞 문자 제거하고, 나머지 문장이 회문인지 확인
3. 위의 1, 2번 경우에 속하지 않는다면 회문이 아님

 

혹시 본인의 코드가 예제 입력은 통과하는데, 틀렸다면 아래 반례 목록을 참고하면 좋을 것 같다!

 

 

예제 입력

abbab

babba

aabcdeddcba
aabab
aapqbcbqpqaa

 

예제 출력

1

1

2

2

1

 

전체 코드

from sys import stdin
input = stdin.readline

num = int(input())
for _ in range(num):
    st = input().strip()
    front, back = 0, len(st) - 1  # 앞, 뒤를 가리키는 포인터
    check = 0

    for _ in range(len(st)):
        if front >= back:
            break
        if st[front] == st[back]:
            front += 1
            back -= 1
            continue

        # 뒷 문자 제거했는데 같을 때, 나머지로 회문 되는지 확인
        if st[front] == st[back-1]:
            temp = st[front:back]
            if temp[:] == temp[::-1]:
                check = 1
                break
        # 앞 문자 제거했는데 같으면
        if st[front+1] == st[back]:
            temp = st[front+1:back+1]
            if temp[:] == temp[::-1]:
                check = 1
                break

        check = 2
        break

    print(check)