[JAVA] 백준 25501 재귀의 귀재

25501번: 재귀의 귀재 (acmicpc.net)

25501번: 재귀의 귀재

 

- 어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있음

- 아래 코드의  isPalindrome 함수는 주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수 

 

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

 

- isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수 구하기 

 

 

풀이 과정 

 

- recursion 함수의 호출 횟수를 구하기 위해 count 전역 변수로 선언

- recursion 함수에서 count 증가 

- isPalindrome 함수에서 count = 0 으로 초기화 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{
	static int count = 0; //recursion 호출 횟수 
	
    public static int recursion(String s, int l, int r){
        count+=1; 
    	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){
    	count=0; //recursion 호출 횟수 초기화 
        return recursion(s, 0, s.length()-1);
    }
    
    public static void main(String[] args) throws IOException
    {
        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	
    	int n = Integer.parseInt(br.readLine());
    	for(int i=0; i<n; i++)
    	{
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		String s = st.nextToken();
    		
    		bw.write(isPalindrome(s)+" "+count);
    		bw.newLine();
    	}
    	
    	bw.flush();
    	bw.close();
    	
    }
}