2-3. 재귀 - 팰린드롬

문제

문제 접근

한 문자열이 팰린드롬인지 판별해야하는데 이를 재귀적으로 처리해야한다.

개인적으로는
1. 맨 처음과 끝을 비교한다.
2-1. 처음과 끝이 다르다면 바로 종료
2-2. 처음과 끝이 같으면 그 부분을 잘라서 문자열 돌려주기

위의 과정을 반복하고 재귀함수가 호출된 개수를 같이 세면 될거 같다.

종료되는 지점은 처음값이 끝값보다 커지는 순간 종료한다.


한가지 고민되는 문제는 처음과 끝을 검사후 재귀함수로 넘길때
문자열을 어떻게 짤라야 하는가가 고민이다.
문자열 전체를 넘기고 index만 변경하여 넘길수도 있는데
이 방법을 사용한다면 굳이 재귀로 푸는 이유가 있을까 싶다.

항상 0과 마지막 인덱스를 비교하고
마지막 조건을 마지막인덱스가 0 or 1인경우에는 리턴을 하자

또한 문자열을 잘라야하니 String 클래스의 substring 매소드를 사용하자

코드

import java.util.Scanner;

public class Main {
    int cnt=0;//호출 횟수를 셀 변수
    
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        Main pL=new Main();
        int flag,N=sc.nextInt();
        String str;
        
        for(int i=0;i<N;i++)
        {
            str=sc.next();
            flag=pL.isPalindrome(str);
            System.out.printf("%d %d\n",flag,pL.cnt);
            pL.cnt=0;
        }
    }

    public int isPalindrome(String str){
        cnt++;

        if(str.length()<=1)
            return 1;//문자열의 글자가 1개거나 0개라면 종료
        if(str.charAt(0)==str.charAt(str.length()-1))
            return isPalindrome(str.substring(1,str.length()-1));
            //만약 맨 처음과 마지막 문자가 같다면 짤라서 다음검사
        else
            return 0;
    }
}

후기

힌트를 보지않고 일단 문제만 본후 내가 구현을 하는 방식으로 진행했다.
다시금 문제를 읽어보니 이미 모든 코드가 다 구현되어있고
recursion 함수가 몇번 호출됬는지를 확인하기만 하면 되었다.

그냥 cnt하나 인스턴스 변수로 건들였으면 되는걸...

그래도 직접 고민하고 구현까지 완성한게 뿌듯하다