[백준] 25501번 : 재귀의 귀재 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

25501번: 재귀의 귀재

 

1. 문제 설명

2. 풀이과정

해당 문제는 팰린드롬인지 파악하는 isPalindrome 함수의 반환값과 그 과정에서 호출된 recursion 함수의 횟수를 구해야 하는 문제이다. isPalindrome 함수의 반환값은 문제에서 주어진 함수를 그대로 가져오면 쉽게 구할 수 있다.

하지만 recursion 함수의 횟수는 구할 수 없다.

하여 각 함수에 cnt라는 새로운 인수를 추가하여 recursion 함수의 횟수를 저장한다.

recursion 함수에서 팰린드롬인지 아닌지 결과를 반환할 때, 기존 함수의 반환인 해당 결과와 recursion 함수의 횟수를 리스트로 묶어 반환한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. cnt 인수를 추가한 recursion 함수를 정의한다. def recursion(s, l, r, cnt)
3. recursion 함수의 횟수를 저장하는 cnt 값을 1 증가시킨다. cnt += 1
4. 이후 함수의 내용은 동일하게 작성한다. if (l >= r)
5. 여기서 반환할 때, 결과와 recursion 함수의 횟수를 리스트로 묶어 반환한다. return [1, cnt]
6. 이후 함수의 내용은 동일하게 작성한다. elif (s[l] != s[r])
7. 여기서도 반환할 때, 결과와 recursion 함수의 횟수를 리스트로 묶어 반환한다. return [0, cnt]
8. 이후 함수의 내용은 동일하게 작성한다. else
9. 여기서도 반환할 때, 기존 recursion 함수의 인수에 cnt를 추가하여 반환한다. return recursion(s, l+1, r-1, cnt)
10. cnt 인수를 추가한 isPalindrome 함수를 정의한다. def isPalindrome(s, cnt)
11. 반환할 때, 기존 recursion 함수의 인수에 cnt를 추가하여 반환한다. return recursion(s, 0, len(s)-1, cnt)
12. 테스트케이스 개수를 입력받는다. T = int(sys.stdin.readline())
13. 테스트케이스 개수만큼 반복하며 for _ in range(T)
14. 알파벳 대문자로 이루어진 문자열을 입력받는다. S = sys.stdin.readline().rstrip()
15. 최종 리스트로 반환되는 결과를 저장할 변수를 생성하고 isPalindrome 함수에 문자열 S와 초기 resursion 함수의 횟수를 인수로 주어 해당 결과를 저장한다. result = isPalindorme(S, 0)
16. 리스트로 반환된 결과를 하나씩 출력한다. print(result[0], result[1])
    

반응형

3. 소스코드

import sys

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

T = int(sys.stdin.readline())

for _ in range(T):
    S = sys.stdin.readline().rstrip()
    
    result = isPalindrome(S, 0)
    print(result[0], result[1])