[백준 알고리즘] 문제 25501번 : 재귀의 귀재

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

25501번: 재귀의 귀재

---

1. 힌트를 참고하자

public class Main{
    public static int recursion(String s, int l, int r){
        if(l >= r) return 1;
        else if(s.charAt(l) != s.charAt(r)) return 0;
        else return recursion(s, l+1, r-1);
    }
    public static int isPalindrome(String s){
        return recursion(s, 0, s.length()-1);
    }
    public static void main(String[] args){
        System.out.println("ABBA: " + isPalindrome("ABBA"));
        System.out.println("ABC: " + isPalindrome("ABC"));
    }
}

위의 코드는 힌트 코드이다.

이 힌트 코드가 이 문제의 흐름을 어떻게 구현해야할 지에 감을 잡게 도와주었다.

이 힌트에서 재귀 부분을 사용하고, 재귀 횟수를 구하는 것은 함수로 하나를 만들어 사용하지 않으려고 한다.

---

2. 재귀 횟수를 세는 변수 선언

우선 재귀 횟수를 세는 것은 굳이 함수를 만들지 않고, static 변수로 선언을 해 주었다. 재귀할 때마다 count를 더해주면 되기 때문이다.

import java.io.*;
import java.util.*;

public class Main{

   // static 변수로 count 선언
    public static int count;

    public static void main(String[] args) throws IOException{}
}

---

3. 팰린드롬인지 판별하는 함수 구현

1️⃣ 재귀를 호출할 때마다 count++ 해준다.

2️⃣ 힌트를 참고하여 코드를 작성한다.

       ☝🏻 startIdx >= lastIdx --> return 1; : Base Case

       ✌🏻 앞에서 시작한 문자열의 문자와 뒤에서 시작한 문자열의 문자열을 비교 --> 같지 않으면 팰린드롭이 아님

       🤟🏻 위의 조건문에 안들어갔다면, 그 다음 순서의 문자를 비교하기 위해 재귀 호출.

 

import java.io.*;
import java.util.*;

public class Main{

   // static 변수로 count 선언
    public static int count;

    public static void main(String[] args) throws IOException{}
    
    // 팰린드롬 판별 함수
    public static void recursion(String str, int startIdx, int lastIdx){
    	// 재귀 호출시 ++
    	count++;
        
        // Base Case
        if(startIdx >= lastIdx){return 1;}
        
        // 시작과 뒤의 문자열의 인덱스의 문자가 다르면 팰린드롭이 아님
        else if(str.charAt(startIdx) != str.charAt(lastIdx)){return 0;}
        
        // 위의 조건문에 안 들어갔으면 문자가 같다는 것.
        // 그러면 다음 문자를 비교해 본다.
        else return recursion(str, startIdx+1, lastIdx-1);
    }
}

---

4. 풀이

import java.io.*;
import java.util.*;

public class Main{

   // static 변수로 count 선언
    public static int count;

    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine()); // 테스트 개수
        
        for(int i = 0; i < T; i++){
            count = 0;
            String str = br.readLine();
            System.out.println(recursion(str, 0, str.length() -1) + " " + count);
        }
    }
    
    // 팰린드롬 판별 함수
    public static void recursion(String str, int startIdx, int lastIdx){
    	// 재귀 호출시 ++
    	count++;
        
        // Base Case
        if(startIdx >= lastIdx){return 1;}
        
        // 시작과 뒤의 문자열의 인덱스의 문자가 다르면 팰린드롭이 아님
        else if(str.charAt(startIdx) != str.charAt(lastIdx)){return 0;}
        
        // 위의 조건문에 안 들어갔으면 문자가 같다는 것.
        // 그러면 다음 문자를 비교해 본다.
        else return recursion(str, startIdx+1, lastIdx-1);
    }
}