[Python] 백준 17609번 - 회문

문제 링크 : https://www.acmicpc.net/problem/17609

17609번: 회문

---

문제

이미지 출처 : https://whatisthenext.tistory.com/98

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

 

예제 입력 :

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

예제 출력 : 

0
1
1
2
2
0
1

 

코드

import sys
input = sys.stdin.readline

T = int(input())
str = []

for i in range(T):
    str.append(input().strip())

def Palindrome(str, depth):
    queue = list(str)
    cnt = 0
    global flag
    flag = 0
    for j in range(int(len(str) / 2)):
        if flag == 1:
            if queue[j + 1] == queue[-(j + 1)]:
                cnt += 1
        elif flag == 2:
            if queue[j] == queue[-(j + 2)]:
                cnt += 1
        elif queue[j] == queue[-(j + 1)]:
            cnt += 1
        elif flag == 0:
            if j + 1 == len(str)-j:
                if queue[j + 2] == queue[-(j + 1)] or queue[j] == queue[-(j + 3)]:
                    flag = 1
                    cnt += 1
            else:
                if queue[j + 1] == queue[-(j + 1)]:
                    flag = 1
                    cnt += 1
                elif queue[j] == queue[-(j + 2)]:
                    flag = 2
                    cnt += 1

    if cnt == int(len(str)/2):
        if flag == 1 or flag == 2:
            return 1
        else:
            return 0
    else:
        if depth == 0:
            if Palindrome(str[::-1], 1) == 1:
                return 1
            return 2

for z in range(T):
    flag = 0
    print(Palindrome(str[z], 0))

 

+ 기억해두기

 

문자열[::-1] 하면 reverse 효과!

 

+ TMI

여러가지 반례! 

1. uuuuau 
여러가지 반례를 해결하다가 갑자기
하나가 빠져서 팰린드롬이 되려면 문자열이 홀수여야하는군!
하는 이상한 생각에 빠져서 홀수 조건을 넣었다가 바로 걸러졌다.

사람이 오래동안 한 문제를 풀다보면
생각이 이상해지기도 하나보다 ㅎ
 
2. baaba
뒤에거를 지우면 되는데 이 반례를 안해줘서 계속 틀렸다ㅠ
그래서 나는 앞에서 했을 때 실패했다면
문자열을 뒤집어서 한 번 더 함수를 실행하도록 하였다!
시간 초과 뜰까봐 조마조마했는데 다행히도 세이프ㅠ

처음에는 재귀를 이용해서 하려고 했었는데
예상과 같이 시간 초과가 떴다 -_-

 

그래서 바로 다 주석처리하고
(지우지 않은건 블로그에 적어두기 위해..ㅎ)
다시 짰다ㅠ

 

결국 경우에 따라 뒤집어서

나름 재귀를 하고 있긴 하지만~ㅎ

한 30-40분 만에 해결할 것 같다.
코딩테스트 준비 초짜 치고 나쁘지 않지 않나~?

ㅎ_ㅎ
앞으로도 화이팅!