C++로 숫자가 미스터리 넘버(Mystery Number)인지 확인하는 방법

이 글에서는 C++을 사용하여 어떤 숫자가 미스터리 넘버(Mystery Number)인지 확인하는 방법을 알아보겠습니다.

미스터리 넘버란 두 개의 수의 합으로 표현할 수 있고, 그 두 수가 서로 자릿수를 뒤집은 관계(예: 29와 92)에 있는 숫자를 의미합니다. 예를 들어 121은 29 + 92 = 121이므로 미스터리 넘버입니다.

확인 알고리즘

미스터리 넘버를 확인하려면 다음 단계를 따릅니다.

단계

1. 1부터 n/2까지의 모든 숫자 i에 대해 반복합니다.
2. 각 i에 대해 자릿수를 뒤집은 숫자 j를 계산합니다.
3. i + j == n이면 n은 미스터리 넘버입니다.
4. 모든 경우를 확인해도 조건을 만족하지 않으면 미스터리 넘버가 아닙니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 숫자의 자릿수를 뒤집는 함수
int revNum(int str) {
    string s = to_string(str);
    reverse(s.begin(), s.end());
    stringstream ss(s);
    int rev = 0;
    ss >> rev;
    return rev;
}

// 미스터리 넘버 여부를 확인하는 함수
bool isMysteryNumber(int n) {
    for (int i = 1; i <= n/2; i++) {
        int j = revNum(i);
        if (i + j == n) {
            cout << i << " " << j;
            return true;
        }
    }
    return false;
}

int main() {
    int num = 121;
    if (isMysteryNumber(num)) {
        cout << "\n" << num << " is a Mystery number";
    } else {
        cout << num << " is not a Mystery number";
    }
}

실행 결과

29 92
121 is a Mystery number

코드 설명

revNum() 함수는 정수를 문자열로 변환한 뒤 reverse()로 자릿수를 뒤집고, 다시 정수로 변환하여 반환합니다. 예를 들어 29를 입력하면 92가 반환됩니다.

isMysteryNumber() 함수는 1부터 n/2까지 반복하면서 각 숫자와 그 숫자를 뒤집은 값의 합이 n과 같은지 검사합니다. n/2까지만 확인해도 충분한 이유는, 두 수 중 하나가 항상 n의 절반 이하이기 때문입니다. 이렇게 하면 불필요한 중복 검사를 줄여 효율성을 높일 수 있습니다.

위 예제에서 121은 29 + 92로 표현되므로 미스터리 넘버임이 확인됩니다. 시간 복잡도는 O(n)이며, 숫자를 문자열로 변환하고 뒤집는 과정이 포함됩니다.