[백준 25501번] 재귀의 귀재

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

25501번: 재귀의 귀재

 

문제 자체는 정말 쉬운 편에 속한다.

어떤 문자열이 주어졌을 때, 팰린드롬인지 아닌지 판별하는 문제인데 게다가 심지어 문제에서 재귀 함수까지 직접 짜서 준다.

재귀함수 호출 횟수도 출력해야 하기 때문에, 주어진 재귀함수에다가 카운트 변수 하나 추가하여서 호출 될 때마다 +1 해주면 끝이다.

 

...라고 생각했으나,

 

계속 5% 대에서 실패

 

다음 코드는 실패가 떴을 때의 제출한 코드이다.

#include <stdio.h>
#include <string.h>
int T;
int cnt;
int recursion(const char *s, int l, int r){
    
    cnt++;
    
    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(void){
    
    scanf("%d",&T);
    
    for(int i=0;i<T;i++){
        cnt=0;
        char str[1001];
        scanf("%s",str);
        printf("%d %d\n",isPalindrome(str),cnt);
    }
}

 

문제에서 주어진 예제도 다 일치하고, 아무리 여러번 봐도 잘못된 부분이 없는 것 같은데 계속 실패가 떴다.

 

처음 알게 된 사실인데, 

printf("%d %d\n",isPalindrome(str),cnt);

출력 함수에서 isPalindrome() 함수가 완전히 종료되기 전에 cnt가 먼저 출력될 수 있다는 점이다.

즉, cnt 변수는 재귀함수가 모두 종료된 후에 최종적으로 남아있는 값이 출력되어야 한다. 가장 마지막으로 호출된 재귀함수까지 카운트를 해주고 나야 총 몇 번 호출되었는지 알 수 있기 때문이다.

 

그런데 함수를 처리할 때 컴파일러 환경에 따라서 인자 순서대로 처리하는 것이 아닌, 랜덤 순서로 처리할 수 있다고 한다.

 

따라서 위 문제를 해결하려면 출력 함수를 두 개를 써서, 팰린드롬 결과를 먼저 출력하고 그 다음 줄에 cnt 변수를 출력하면 된다.

 

 

수정 후 :

#include <stdio.h>
#include <string.h>
int T;
int cnt;
int recursion(const char *s, int l, int r){
    
    cnt++;
    
    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(void){
    
    scanf("%d",&T);
    
    for(int i=0;i<T;i++){
        cnt=0;
        char str[1001];
        scanf("%s",str);
        printf("%d ",isPalindrome(str));
        printf("%d\n",cnt);
    }
}

 

 

기존과 달리,

        printf("%d ",isPalindrome(str));
        printf("%d\n",cnt);

 

print문을 두개로 나누어서 출력을 하니 정답이 되었다.