[Python] 백준 풀기 25501 - 재귀의 귀재

파이썬 백준 25501번

브론즈2

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

25501번: 재귀의 귀재

 

 

 

문제 보기

 

안으로 파고 파고 파고 드는 재귀 함수 형태를 이해하자.

 

int recursion(const char *s, int l, int r){
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(const char *s){
    return recursion(s, 0, strlen(s)-1);
}

 

 

 

문제 풀기

풀이 감이 안와 힌트를 적극 활용하였다.

 

주어진 힌트의 코드로 작동방식을 이해하니 코딩 뉴비로써 정말 재밌는 알고리즘임을 느꼈다.

함수 recursion() 안에서 양 끝단의 문자의 위치가 교차될 때까지 recursion() 을 재귀로 계속 돌리고,

이때 양쪽 알파벳을 비교하는 elif s[l] != s[r]: 라는 허들을 넘어야 한다.

이 모습은 마치 좌우대칭 쌍둥이 어린이들이 일렬로 서있고 이를 긴 줄넘기로 매 순간 뛰는 모습이 그려졌다.

초등학교 때의 운동회 기억처럼..

이때 코딩 문제의 규칙에서는 양 끝단이 쌍둥이 일 때 통과.

 

힌트를 적극 활용하여 풀이하기 위해서

변수 count 를 추가.

함수 recursion() 에 count += 1 을 추가하여 매번 함수가 실행될 때마다 +1 이 되게 함.

이렇게 풀면서 return 으로 s 와 count 가 어떻게 나오는지 어떤 자료형으로 나오는지 공부가 됨.

def recursion(s, l, r, count): 와 def isPalindrome(s, count): 모두 튜플 자료형으로 반환하고,

두 변수 모두 한 번에 프린트할 수 있었음.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

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

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

T = int(inputdata())
for _ in range(T):
    s = inputdata().strip()
    
    count = 0
    s, count = isPalindrome(s, count)
    
    print(s, count)



# 5
# AAA
# ABBA
# ABABA
# ABCA
# PALINDROME

# 1 2
# 1 3
# 1 3
# 0 2
# 0 1