[백준] 25501번: 재귀의 귀재 (Java)

1. 문제설명

문제에서 주어진 팰린드롬(앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열)을 판별하는 isPalindrome 함수와 recursion 함수를 이용하여, 주어진 문자열에 대해 팰린드롬의 여부와 recursion 함수의 호출 횟수를 출력하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 1024MB

 

2. 접근 방식

• 문제에서 주어진 isPalindrome, recursion 함수를 자바 코드로 수정한다.
• isPalindrome 함수
  • recursion 함수를 호출하여 팰린드롬 여부를 검사하는 함수이다.
  • 문자열과 시작인덱스, 끝 인덱스를 인자로 recursion 함수를 호출한다.
• recursion 함수
  • 문자열이 팰린드롬인지 재귀적으로 확인하는 함수이다.
  • 왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같으면 1을 반환한다. (팰린드롬 O)
  • 양 끝 문자가 다르면 0을 반환한다. (팰린드롬 X)
  • 양 끝 문자가 같으면 왼쪽 인덱스 1증가, 오른쪽 인덱스 1 감소시켜 재귀 호출한다.
• recursion 함수의 호출 횟수를 구하기 위해 static 변수 count를 사용한다.
  • 매 테스트 케이스에서 1로 초기화한다.
  • recursion 함수에서 재귀 호출 시 count를 1 증가시킨다.

 

 

3. 최종 코드

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

public class Main {
    static int count; // recursion 함수의 호출 횟수

    // 문자열이 팰린드롬인지 재귀적으로 확인하는 함수
    static int recursion(String str, int l, int r) {
        if(l >= r) return 1; // 왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같으면 팰린드롬 O
        else if(str.charAt(l) != str.charAt(r)) return 0; // 양 끝 문자가 다르면 팰린드롬 X
        else {
            count++; // 호출 횟수 증가
            return recursion(str, l+1, r-1); // 다음 검사할 인덱스로 재귀 호출
        }
    }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        for(int i=0; i<t; i++) {
            String str = br.readLine();
            count = 1; // 각 테스트마다 count 초기화 (초기 호출 1포함)
            sb.append(isPalindrome(str)+" "+count+"\\n"); // 결과 StringBuilder에 추가
        }
        System.out.println(sb);
    }
}

 

4. 시간복잡도

recursion 함수의 시간복잡도가 $O(n/2) => O(n)$.

따라서 전체 시간복잡도는 $O(t * n)$이다. ($t$는 테이스케이스 수)