C 언어로 배열이 회문(Palindrome)인지 확인하는 방법

배열 회문 검사란?

임의의 크기 n을 갖는 배열 arr[]가 주어졌을 때, 이 배열이 회문(palindrome)인지 아닌지 판별하는 것이 목표입니다. 회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 완전히 같은 수열을 의미합니다. 예를 들어 MADAM, NAMAN과 같은 단어나 {1, 0, 0, 1}처럼 좌우 대칭을 이루는 배열이 대표적입니다.

배열이 회문인지 확인하는 가장 기본적인 방법은 두 개의 포인터(인덱스)를 활용하는 것입니다. 하나는 배열의 시작 위치에서, 다른 하나는 끝 위치에서 출발해 서로 마주 보는 요소들을 한 쌍씩 비교해 나갑니다.

예제

입력: arr[] = {1, 0, 0, 1}
출력: 배열은 회문입니다
입력: arr[] = {1, 2, 3, 4, 5}
출력: 배열은 회문이 아닙니다

접근 방법

배열의 첫 번째 요소와 마지막 요소부터 비교를 시작해, 두 인덱스가 배열의 중간에서 만날 때까지 안쪽으로 이동하며 나머지 요소들도 차례대로 비교합니다. 모든 요소 쌍이 일치하면 해당 배열은 회문이며, 단 하나의 쌍이라도 값이 다르면 회문이 아닙니다.

알고리즘

시작
함수 int isPalindrome(int arr[], int n)
    단계 1 → 변수 i, j, flag 선언 후 flag를 0으로 초기화
    단계 2 → i = 0, j = n-1로 설정하고, i가 j보다 작은 동안 i는 증가, j는 감소하며 반복
        만약 arr[i] != arr[j]이면
            flag를 1로 설정
            반복 중단(break)
        조건문 종료
    반복문 종료
    단계 3 → flag == 1이면
        0을 반환
    단계 4 → 그렇지 않으면
        1을 반환
함수 종료
함수 int main()
    단계 1 → arr[]를 {1, 0, 2, 3, 2, 2, 1}로 선언 및 초기화
    단계 2 → n을 sizeof(arr)/sizeof(arr[0])로 계산하여 초기화
    단계 3 → isPalindrome(arr, n)이 참이면
        "배열은 회문입니다" 출력
    단계 4 → 그렇지 않으면
        "배열은 회문이 아닙니다" 출력
    0 반환
main 함수 종료
종료

구현 코드

#include <stdio.h>

// 배열이 회문이면 1, 아니면 0을 반환하는 함수
int isPalindrome(int arr[], int n) {
   int i, j, flag = 0;
   // 앞쪽 인덱스 i와 뒤쪽 인덱스 j를 이동하며 요소를 비교
   for(i = 0, j = n - 1; i < j; i++, j--) {
      if(arr[i] != arr[j]) {
         flag = 1;
         break;
      }
   }
   if(flag == 1)
      return 0;
   else
      return 1;
}

int main() {
   int arr[] = {1, 0, 2, 3, 2, 2, 1};
   int n = sizeof(arr) / sizeof(arr[0]);
   if(isPalindrome(arr, n)) {
      printf("배열은 회문입니다\n");
   } else {
      printf("배열은 회문이 아닙니다\n");
   }
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

배열은 회문이 아닙니다

예제 배열 {1, 0, 2, 3, 2, 2, 1}을 거꾸로 뒤집으면 {1, 2, 2, 3, 2, 0, 1}이 되어 원본 배열과 일치하지 않습니다. 따라서 이 배열은 회문이 아니라고 판별됩니다.

복잡도 분석

이 알고리즘은 배열의 절반만큼만 순회하므로 시간 복잡도는 O(n)이며, 별도의 보조 배열 없이 몇 개의 변수만 사용하기 때문에 공간 복잡도는 O(1)입니다.