크기가 n인 배열 arr[n]이 주어졌을 때, 재귀(recursion)를 사용하여 이 배열이 회문(palindrome)인지 아닌지 판별하는 것이 목표입니다. 회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 수열이나 문자열을 의미하며, 대표적인 예로 MADAM, NAMAN 등이 있습니다.
배열이 회문인지 확인하려면 배열의 시작 부분과 끝 부분에서 동시에 출발하여 요소를 하나씩 비교해 나가면 됩니다.
재귀 방식에서도 마찬가지로 start와 end 값을 조금씩 변경해 가며 비교를 반복합니다. 두 인덱스가 서로 만나거나 교차할 때까지 모든 값이 일치하면 회문이고, 중간에 값이 다르면 즉시 종료하고 false를 반환하여 주어진 배열이 회문이 아님을 알립니다.
예시
입력: arr[] = { 2, 3, 4, 3, 2}
출력: Yes, the array is Palindrome
설명: 배열의 처음(2, 3, 4, 3, 2)과 끝(2, 3, 4, 3, 2)이 동일합니다.
입력: arr[] = {1, 2, 3, 4}
출력: No, the array is not Palindrome
설명: 배열의 처음(1, 2, 3, 4)과 끝(4, 3, 2, 1)이 동일하지 않습니다.접근 방식
다음 단계를 재귀적으로 수행합니다.
- arr[start]와 arr[end]가 같은지, 그리고 start < end인지 확인합니다.
- start는 1 증가시키고, end는 1 감소시킵니다.
- 1단계로 돌아가 위 과정을 반복합니다.
알고리즘
시작
함수 int palindrome(int arr[], int start, int end) 내부
단계 1 -> 만약 start >= end라면,
1을 반환한다
단계 2 -> 만약 arr[start] == arr[end]라면,
palindrome(arr, start + 1, end - 1)을 반환한다
단계 3 -> 그렇지 않으면 {
0을 반환한다
함수 int main() 내부
단계 1 -> 배열 arr[]를 선언하고 초기화한다
단계 2 -> n = sizeof(arr) / sizeof(arr[0])을 선언하고 초기화한다
단계 3 -> 만약 palindrome(arr, 0, n - 1)의 결과가 1이라면,
"Yes, the array is Palindrome"을 출력한다
단계 4 -> 그렇지 않으면
"No, the array is not Palindrome"을 출력한다
종료C 코드 구현
#include <stdio.h>
// 회문이면 1, 아니면 0을 반환하는 재귀 함수
int palindrome(int arr[], int start, int end) {
// 기저 사례: start가 end보다 크거나 같으면 모든 비교가 완료된 것
if (start >= end) {
return 1;
}
// 양쪽 끝의 값이 같으면 안쪽 요소들을 재귀적으로 비교
if (arr[start] == arr[end]) {
return palindrome(arr, start + 1, end - 1);
} else {
// 값이 다르면 회문이 아님
return 0;
}
}
// 드라이버 코드
int main() {
int arr[] = { 1, 2, 0, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
if (palindrome(arr, 0, n - 1) == 1)
printf("Yes, the array is Palindrome\n");
else
printf("No, the array is not Palindrome\n");
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Yes, the array is Palindrome
복잡도 분석
시간 복잡도: O(n) — 배열 길이의 절반에 해당하는 횟수만큼 재귀 호출이 발생합니다.
공간 복잡도: O(n) — 재귀 호출에 따른 호출 스택 공간이 사용됩니다.