[5주차 기본문제 3] 재귀의 귀재

문제 설명

주어진 문제는 문자열이 팰린드롬인지 확인하는 것입니다. 팰린드롬은 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 말합니다. 이 문제는 재귀적인 방법을 사용하여 해결해야 합니다.

제한 조건

• 문자열의 길이는 최대 1000입니다.
• 주어지는 문자열은 알파벳 대문자로만 구성됩니다.

입출력 예

입력	출력
ABBA	1 4
ABC	0 3

---

문제 해결 방법

해결 전략

1. 문자열이 팰린드롬인지 확인하는 재귀 함수를 작성합니다.
2. 재귀 함수는 문자열의 시작과 끝 문자가 동일한지 확인합니다.
3. 동일하면 다음 비교를 위해 시작과 끝을 한 칸씩 좁혀가며 재귀 호출합니다.
4. 다르면 팰린드롬이 아님을 반환합니다.
5. 문자열이 팰린드롬인지 여부와 함께 재귀 호출 횟수를 반환합니다.

---

코드 구현

다음은 팰린드롬을 확인하는 Python 코드입니다.

def recursion(s, l, r, count):
    count[0] += 1
    if l >= r:
        return 1
    elif s[l] != s[r]:
        return 0
    else:
        return recursion(s, l + 1, r - 1, count)

def isPalindrome(s):
    count = [0]
    result = recursion(s, 0, len(s) - 1, count)
    return result, count[0]

# 입력을 받습니다.
T = int(input())
for _ in range(T):
    s = input().strip()
    result, cnt = isPalindrome(s)
    print(result, cnt)

코드 설명

• recursion 함수는 문자열 s의 시작 인덱스 l과 끝 인덱스 r을 비교합니다. 또한, 재귀 호출 횟수를 기록하기 위해 count 리스트를 사용합니다.
• isPalindrome 함수는 recursion 함수를 호출하여 팰린드롬 여부와 재귀 호출 횟수를 계산합니다.
• 입력 문자열의 개수를 받아 각 문자열에 대해 팰린드롬 여부와 재귀 호출 횟수를 출력합니다.

예시 테스트

• 입력:

  2
  ABBA
  ABC

• 출력:

  1 4
  0 3

이 코드는 주어진 모든 조건을 만족하며, 각 입력에 대해 올바르게 팰린드롬 여부와 재귀 호출 횟수를 출력합니다.

---

결론

이 문제는 재귀를 사용하여 문자열이 팰린드롬인지 확인하는 방법을 익히는 좋은 연습입니다. 제한 조건이 비교적 간단하므로 재귀 호출을 통해 문제를 쉽게 해결할 수 있습니다. 주어진 코드와 전략을 활용하여 문제를 해결할 수 있으며, 이를 백준 온라인 저지에 제출하여 올바르게 작동함을 확인할 수 있습니다.