BOJ 25501 - 재귀의 귀재

문제

문자열이 팰린드롬인지 재귀 함수로 판별하되, 재귀 호출 횟수도 함께 출력하라.

입력

첫째 줄에 테스트 케이스 수 T, 이후 T개의 문자열이 주어진다.

출력

각 문자열에 대해 팰린드롬이면 1, 아니면 0과 재귀 호출 횟수를 공백으로 구분하여 출력한다.

예제

입력	출력
`2` `AAA` `ABBA`	`1 2` `1 2`

풀이

양 끝에서 중앙으로 좁혀가며 재귀적으로 팰린드롬을 판별하고, 호출 횟수를 카운트한다.

시작 인덱스 st와 끝 인덱스 ed를 설정한다
재귀 호출마다 cnt를 증가시킨다
st가 ed 이상이면 팰린드롬(1), 양 끝 문자가 다르면 비팰린드롬(0)을 반환한다
양 끝이 같으면 recur(s, st+1, ed-1)로 안쪽을 비교한다

핵심 아이디어: 양 끝에서 중앙으로 한 칸씩 좁혀가므로 최대 N/2번 재귀 호출된다.

코드

package day699;
 
import java.io.*;
 
public class Day684BOJ25501재귀의귀재 {
 
  static int cnt = 0;
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    int T = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < T; i++) {
      String S = br.readLine();
      cnt = 0;
      sb.append(isPalindrome(S)).append(" ").append(cnt).append("\n");
    }
    br.close();
    System.out.print(sb);
  }
 
  static int isPalindrome(String s) {
    return recur(s, 0, (s.length() - 1));
  }
 
  static int recur(String s, int st, int ed) {
    cnt++;
 
    if (st >= ed)
      return 1;
    else if (s.charAt(st) != s.charAt(ed))
      return 0;
    else
      return recur(s, (st + 1), (ed - 1));
  }
}

복잡도

시간: O(N)
공간: O(N)

문제