리스트에서 모든 회문(Palindrome) 숫자 찾기 - C++ 구현 방법

이번 글에서는 간단한 프로그래밍 문제를 다뤄보겠습니다. 주어진 리스트(배열) 안에서 회문(Palindrome)에 해당하는 모든 숫자를 찾아 출력하는 것이 목표입니다.

회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열이나 숫자를 의미합니다. 예를 들어 121, 111, 858처럼 숫자를 거꾸로 뒤집어도 원래 값과 동일한 수가 바로 회문 숫자입니다.

접근 방식

해결 방법은 매우 직관적입니다. 리스트의 각 숫자를 하나씩 꺼내 해당 숫자가 회문인지 검사하고, 회문이라면 화면에 출력하면 됩니다.

알고리즘: getAllPalindrome(arr, n)

Begin
    for each element e in arr, do
        if e is palindrome, then
            print e
        end if
    done
End

C++ 코드 예제

먼저 isPalindrome() 함수는 숫자를 자릿수 단위로 분리하여 역순으로 뒤집은 뒤, 원래 값과 비교하는 방식으로 회문 여부를 판별합니다. 이후 getAllPalindrome() 함수가 배열을 순회하며 회문인 요소만 출력합니다.

#include <iostream>
#include <cmath>
using namespace std;
bool isPalindrome(int n){
    int reverse = 0, t;
    t = n;
    while (t != 0){
        reverse = reverse * 10;
        reverse = reverse + t%10;
        t = t/10;
    }
    return (n == reverse);
}
int getAllPalindrome(int arr[], int n) {
    for(int i = 0; i<n; i++){
        if(isPalindrome(arr[i])){
            cout << arr[i] << " ";
        }
    }
}
int main() {
    int arr[] = {25, 145, 85, 121, 632, 111, 858, 45};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "All palindromes: ";
    getAllPalindrome(arr, n);
}

실행 결과

All palindromes: 121 111 858

예제 배열 {25, 145, 85, 121, 632, 111, 858, 45} 중에서 뒤집어도 같은 값이 되는 숫자는 121, 111, 858 세 개입니다. 이처럼 시간 복잡도는 O(n × d)로, n은 배열의 크기, d는 숫자의 자릿수를 의미하며 매우 효율적인 편입니다.