백준 25501번 문제 함수 호출 횟수 계산 -python

백준 문제 단계별로 풀기 중 재귀 단계에 있는 문제이다.

 

문제 자체는 재귀 함수를 주어주고 푸는 문제라 쉬운데 

 

여기서 함수가 몇 번 호출됐는지 구하는 것이 나와 풀이도 기억할 겸해서 들고 왔다.

 

---

백준 25501번

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

정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다.

팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다.

어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 아래 코드의 isPalindrome 함수는 주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다.

#include <stdio.h>
#include <string.h>

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);
}

int main(){
    printf("ABBA: %d\n", isPalindrome("ABBA")); // 1
    printf("ABC: %d\n", isPalindrome("ABC"));   // 0
}

정휘는 위에 작성된 isPalindrome 함수를 이용하여 어떤 문자열이 팰린드롬인지 여부를 판단하려고 한다.

구체적으로는, 문자열 S$S$를 isPalindrome 함수의 인자로 전달하여 팰린드롬 여부를 반환값으로 알아낼 것이다. 더불어 판별하는 과정에서 recursion 함수를 몇 번 호출하는지 셀 것이다.

정휘를 따라 여러분도 함수의 반환값과 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'))

python3로 주는 힌트도 있기에 훨씬 간편하게 풀 수 있다.

 

여기에 함수 호출 횟수만 구해주면 된다.

 

python에서의 counter 함수를 쓰면 손쉽게 함수 호출 횟수를 구할 수 있다.

 

함수의 이름에 .counter만 붙여주면 된다.

def recursion(s, l, r):
  # 함수 호출 횟수
    recursion.counter += 1

이렇게 함수 안에 넣어두고

 

전역변수로도 초기화시켜준다.

 

def recursion(s, l, r):
  # 함수 호출 개수세기
    recursion.counter += 1
    ...
    
recursion.counter = 0

출력 시에는 함수이름.counter 로 해주면 된다.

 

---

정답

import sys

def recursion(s, l, r):
  # 함수 호출 개수세기
    recursion.counter += 1
    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)-2)

T = int(input())

recursion.counter = 0

for _ in range(T):
  s = str(sys.stdin.readline())
  print(isPalindrome(s), recursion.counter)
  s = []
  recursion.counter = 0