백준 25501번 [재귀의 귀재](C++) -yes6686- 티스토리

백준 문제 풀이: 25501 [재귀의 귀재]

---

문제 링크: https://www.acmicpc.net/problem/25501

문제 설명:

주어진 문자열이 팰린드롬인지 확인하는 문제입니다. 팰린드롬 여부를 확인하는 과정에서 재귀 호출 횟수도 함께 출력해야 합니다.

팰린드롬이란, 앞에서 읽으나 뒤에서 읽으나 같은 문자열을 말합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int cnt; // 재귀 호출 횟수

// 재귀적으로 팰린드롬 여부를 확인
int recursion(string &s, int l, int r) {
    cnt++; // 호출 횟수 증가
    if (l >= r) return 1; // 중앙에 도달하면 팰린드롬
    else if (s[l] != s[r]) return 0; // 좌우 문자가 다르면 팰린드롬 아님
    else return recursion(s, l + 1, r - 1); // 양쪽에서 한 칸씩 좁힘
}

// 팰린드롬 확인 함수
int isPalindrome(string &s) {
    return recursion(s, 0, s.size() - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T; // 테스트 케이스 수
    cin >> T;

    while (T--) {
        string s;
        cin >> s; // 문자열 입력
        cnt = 0; // 호출 횟수 초기화
        cout << isPalindrome(s) << ' ' << cnt << '\n'; // 결과와 호출 횟수 출력
    }

    return 0;
}

예제 입력:

5
AAA
ABBA
ABABA
ABCA
PALINDROME

예제 출력:

1 2
1 3
1 3
0 2
0 1

---

코드 설명

• 핵심 알고리즘: 재귀적으로 문자열의 양 끝에서부터 비교하여 팰린드롬 여부를 확인합니다.
• 구현 세부사항:
  • 좌우 문자가 같으면 한 칸씩 좁혀가며 비교를 반복합니다.
  • 좌우 문자가 다르면 즉시 팰린드롬이 아님을 반환합니다.
  • 재귀 호출 횟수를 추적하여 함께 출력합니다.
• 시간 복잡도:
  • 문자열 길이를 n이라 할 때, 최악의 경우 O(n)번 호출됩니다.

---

결과

입력된 문자열이 팰린드롬인지 여부와 재귀 호출 횟수를 정확히 계산하여 출력합니다. 문제는 재귀 호출의 원리를 이해하고 추적하는 데 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!