C++에서 문자열 없이 정수가 회문(Palindrome)인지 확인하는 방법

문제 개요

음수가 아닌 정수 num이 주어졌을 때, 이 숫자가 회문(palindrome)인지 판별하는 프로그램을 작성해야 합니다. 단, 중요한 조건은 문자열을 사용하지 않고 숫자 연산만으로 해결해야 한다는 점입니다.

예를 들어 입력값이 1331이라면, 앞에서부터 읽어도 뒤에서부터 읽어도 같은 수이므로 결과는 true(참)가 됩니다.

접근 방법

핵심 아이디어는 간단합니다. 숫자의 각 자릿수를 하나씩 추출하여 그 숫자 자체를 뒤집은 값(reversed number)을 만들고, 원래 숫자와 비교하는 것입니다.

구체적인 알고리즘은 다음과 같습니다.

결과를 저장할 변수 ret을 0으로 초기화합니다.
원래 값을 보관하기 위해 x = num으로 복사해 둡니다.
num이 0보다 큰 동안 다음 과정을 반복합니다.
- d = num % 10: 마지막 자릿수를 추출합니다.
- ret = ret * 10: 기존 결과를 한 자리 왼쪽으로 밀어냅니다.
- ret = ret + d: 추출한 자릿수를 새 자리에 추가합니다.
- num = num / 10: 처리한 자릿수를 제거합니다.
반복이 끝나면 x(원래 값)와 ret(뒤집힌 값)이 같으면 true를 반환하고, 다르면 false를 반환합니다.

예를 들어 1331의 경우: 첫 반복에서 d=1, ret=1 → 두 번째에서 d=3, ret=13 → 세 번째에서 d=3, ret=133 → 네 번째에서 d=1, ret=1331이 되어 원래 값과 일치하므로 회문임을 알 수 있습니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool solve(int num) {
        int ret = 0;
        int x = num;
        while(num > 0){
            int d = num % 10;
            ret *= 10;
            ret += d;
            num /= 10;
        }
        return x == ret;
    }
};
main() {
    Solution ob;
    cout << (ob.solve(1331));
}

입력

출력

시간 및 공간 복잡도

이 알고리즘은 숫자의 자릿수만큼만 반복하므로 시간 복잡도는 O(log₁₀ n), 즉 자릿수에 비례하며, 추가 공간은 상수 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 문자열 변환 없이 순수 산술 연산만 사용하기 때문에 매우 효율적인 방법입니다.