문제 출처

단계별로 풀어보기 > 재귀 > 재귀의 귀재
https://www.acmicpc.net/problem/25501

문제 설명

테스트 케이스 T개가 주어질 때, 해당 테스트 케이스를 isPalindrome 함수를 진행하여 팰린드롬이면 1, 아닐 경우 0 그리고 isPalindrome 함수를 각각 몇 번 호출하였는지 출력하라.

접근 방법

import java.io.*;

public class 재귀의_귀재 {
    public static int count;
    public static int isPalindrome(int left,int right, String str){
        if(left>=right){
            count++;
            return 1;
        }

        if(str.charAt(left) == str.charAt(right)){
            count++;
            return isPalindrome(left+1,right-1,str);
        }else{
            count++;
            return 0;
        }
    }

    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 T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i<T; i++){
            count = 0;
            String str = br.readLine();
            int pal = isPalindrome(0,str.length()-1,str);

            sb.append(pal).append(" ").append(count).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }
}

Review

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

public class 재귀의_귀재_review {

    public static int count;

    public static int isPalindrome(String s, int left, int right){
        count++;
        if(left >= right){
            return 1;
        }
        if(s.charAt(left) == s.charAt(right)) return isPalindrome(s,left+1, right-1) ;
        return 0;
    }

    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 T = Integer.parseInt(br.readLine());


        StringBuilder sb = new StringBuilder();
        for(int i =0; i<T; i++){
            count = 0;
            String st = br.readLine();

            int result = isPalindrome(st,0,st.length()-1);

            sb.append(result).append(" ").append(count).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }

}

알게된 점

처음엔 isPalindrome 함수 안에 count를 세서 출력하려했으나 문제를 보니 isPalindrome은 1,0을 return 해야 구조가 더 편한 것 같아서 count 필드를 만들어서 count를 반복문마다 초기화하는 방식을 택했다.

Review
isPalindrome 메서드에 마지막 left와 right가 같은 경우 return을 빼먹었었다.

문제푼 흔적

Review