C++ 재귀 함수로 문자열 회문(팰린드롬) 판별하기
문자열 Str이 입력으로 주어졌을 때, 재귀 함수를 이용해 해당 문자열이 회문(palindrome)인지 아닌지 판별하는 것이 이 글의 목표입니다.
회문 문자열이란 앞에서부터 읽어도 뒤에서부터 읽어도 동일한 단어가 되는 문자열을 의미합니다. 길이가 0인 문자열 역시 회문으로 간주합니다. 즉, 회문을 문자 단위로 뒤집으면 원래 문자열과 완전히 같아집니다.
회문의 대표적인 예로는 madam, abcba, malayalam 등이 있습니다.
예시
예제 1
입력 − Str = "malayalam"
출력 − 입력 문자열은 회문입니다.
설명 −
Str[0 ~ 8] = malayalam
뒤집은 문자열 Str[8 ~ 0] = malayalam
두 문자열이 서로 동일합니다.
예제 2
입력 − Str = "tutorial"
출력 − 입력 문자열은 회문이 아닙니다.
설명 −
Str[0 ~ 7] = tutorial
뒤집은 문자열 Str[7 ~ 0] = lairotut
두 문자열이 서로 다릅니다.
프로그램의 접근 방식
이 방식에서는 먼저 문자열이 한 글자만 담고 있는지 확인합니다. 그렇다면 곧바로 회문으로 판단하고, 그렇지 않다면 나머지 문자들을 재귀적으로 순회합니다. 이때 서로 대응되는 문자가 하나라도 다르면 재귀를 중단합니다.
- 입력 문자열 Str[]을 받아 길이를 계산합니다.
- 길이가 0이면 result = 1로 설정합니다.
- 그렇지 않으면 result = checkPalindrome(Str, 0, length - 1)을 호출합니다. 여기서 0은 첫 번째 인덱스, length - 1은 마지막 인덱스입니다.
- checkPalindrome(char str[], int first, int last) 함수는 문자열 내 어떤 문자든 대응 위치의 문자와 일치하지 않으면 0을 반환합니다.
- first와 last 인덱스가 같다는 것은 문자열이 한 글자뿐이라는 뜻이므로 1을 반환합니다.
- 그렇지 않으면 first++, last--로 양 끝 문자를 제외한 나머지 부분을 검사하기 위해 checkPalindrome(str, first, last)를 재귀 호출합니다.
- 모든 재귀 호출이 종료되면 최종 결과를 얻게 됩니다.
- 결과가 1이면 입력 문자열은 회문입니다.
- 그렇지 않으면 입력 문자열은 회문이 아닙니다.
- main 함수에서 결과를 출력합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
int checkPalindrome(char str[], int first, int last){
if (first < last + 1){
first++;
last--;
return checkPalindrome(str, first, last);
}
if (first == last){
return 1;
}
if (str[first] != str[last]){
return 0;
}
return 1;
}
// Driver Code
int main(){
char Str[] = "madam";
int result;
int length = strlen(Str);
if (length == 0){
result = 1;
}
else{
result = checkPalindrome(Str, 0, length - 1);
}
if (result == 1){
cout << "Input string is palindrome.";
}
else{
cout << "Input string is not a palindrome.";
}
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Input string is palindrome.