[Python] 파이썬 백준(25501) 재귀의 귀재

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

25501번: 재귀의 귀재

---

나의 풀이

문자열이 팰린드롬인지 판별하며, recursion이 얼마나 호출됐는지를 출력하는 문제

팰린드롬은 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때 같은 문자열을 말함

힌트

def recursion(s, l, r):
    if l >= r: return 1
    elif s[l] != s[r]: return 0
    else: return recursion(s, l+1, r-1)

def isPalindrome(s):
    return recursion(s, 0, len(s)-1)

print('ABBA:', isPalindrome('ABBA'))
print('ABC:', isPalindrome('ABC'))

---

재귀를 사용하여 문제를 해결하였고 global을 통해 전역변수를 함수 안에서도 쓸 수 있게 하였다.

import sys
cnt = int(sys.stdin.readline())

def recursion(s):
    global answer
    answer += 1
    if len(s) <= 1: return 1
    if s[0] != s[-1]: return 0
    return recursion(s[1:-1])

for _ in range(cnt):
    answer = 0
    s = sys.stdin.readline()[:-1]
    print(recursion(s), answer)

---

다른 사람의 풀이

예시로 재귀로 주었기 때문에 재귀를 쓰지 않을 때 풀이법을 생각해보지 않았는데 Python으로 압도적으로 적은 시간이 나온 코드가 있어 가져왔다.

• input을 2차원 배열 형태로 받고 a [::-1](역순 변환)을 통해 팰린드롬을 확인함
• 팰린드롬이 아니라면 몇번째에서 팰린드롬이 끝나는지 탐색함

n = int(input())
s = [input() for i in range(n)]

for i in range(n):
    if s[i] == s[i][::-1]:
        print(1,1+len(s[i])//2)
    else:
        print(0 ,end=" ")
        s_ = s[i][::-1]
        cnt = 1
        for k in range(len(s[i])):
            if s[i][k] != s_[k]:
                print(cnt)
                break
            else:
                cnt+=1