백준 25501 재귀의 귀재 Java: 팰린드롬 결과와 호출 횟수 세기

백준 25501번 ‘재귀의 귀재’는 재귀 함수로 문자열이 팰린드롬인지 판단하고, 재귀 함수가 몇 번 호출됐는지도 함께 출력하는 문제다. 양끝 문자를 비교한 뒤 범위를 한 칸씩 좁히고, 함수에 들어올 때마다 count를 늘리면 된다.

• 백준 25501번 재귀의 귀재

종료 조건과 호출 횟수

recursion(s, left, right)는 다음 순서로 동작한다.

1. 함수에 들어오자마자 호출 횟수를 1 늘린다.
2. left >= right면 가운데까지 비교한 것이므로 1을 반환한다.
3. 양끝 문자가 다르면 팰린드롬이 아니므로 0을 반환한다.
4. 같으면 left + 1, right - 1 범위로 다시 호출한다.

호출 횟수는 비교 횟수와 비슷하지만 완전히 같지는 않다. 홀수 길이 문자열은 마지막에 가운데 한 글자인 상태로 함수가 한 번 더 호출되고, 짝수 길이는 pointer가 교차한 상태로 한 번 더 호출된다.

예를 들어 ABBA는 다음 세 번 호출된다.

recursion("ABBA", 0, 3)
recursion("ABBA", 1, 2)
recursion("ABBA", 2, 1)

결과는 팰린드롬 1, 호출 횟수 3이다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static int callCount;

    private static int recursion(String text, int left, int right) {
        callCount++;

        if (left >= right) {
            return 1;
        }

        if (text.charAt(left) != text.charAt(right)) {
            return 0;
        }

        return recursion(text, left + 1, right - 1);
    }

    private static int isPalindrome(String text) {
        return recursion(text, 0, text.length() - 1);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringBuilder output = new StringBuilder();

        int testCount = Integer.parseInt(reader.readLine());

        for (int test = 0; test < testCount; test++) {
            String text = reader.readLine();
            callCount = 0;

            int result = isPalindrome(text);
            output.append(result)
                    .append(' ')
                    .append(callCount)
                    .append('\n');
        }

        System.out.print(output);
    }
}

각 문자열을 검사하기 전에 callCount = 0으로 초기화해야 한다. 원문 코드에 있던 int[][] answer는 실제 계산과 출력에 사용되지 않아 제거했다. 백준 제출 형식에 맞춰 class 이름도 Main으로 정리했다.

예제로 호출 흐름 확인하기

5
AAA
ABBA
ABABA
ABCA
PALINDROME

1 2
1 3
1 3
0 2
0 1

PALINDROME은 첫 글자 P와 마지막 글자 E가 바로 다르므로 한 번만 호출하고 0을 반환한다. ABCA는 바깥의 A가 같아 한 단계 들어간 뒤 B와 C가 달라져 두 번 호출한다.

복잡도와 재귀 깊이

문자열 길이를 L이라고 하면 양끝 pointer가 안으로 이동하므로 최악의 시간 복잡도는 O(L)이다. call stack도 최악에 O(L) 공간을 사용한다.

원문을 작성할 당시에는 재귀를 BFS와 DFS로 넘어가기 전에 익혀야 할 기본기라고 적어 두었다. 실제로 traversal code를 읽을 때 종료 조건, 상태 변화, 호출 순서를 구분하는 습관은 그대로 이어진다. 반복 구조로 구현한 BFS는 백준 24444·24445 방문 순서, 지수를 반으로 줄이는 재귀는 백준 1629 곱셈에서 비교할 수 있다.

검증 범위

Java source를 수동 검토하고 보존된 예제 출력 및 문자열 길이 1부터 8까지의 모든 A·B 조합을 반복문 oracle과 대조했다. 2026년 8월 2일 현재 BOJ URL은 채점 서비스 준비 화면이라 current judge 제출은 검증하지 못했다.