C++로 숫자가 뒤죽박죽(Jumbled) 숫자인지 확인하는 방법

이번 글에서는 흥미로운 문제 하나를 살펴보겠습니다. 바로 주어진 숫자가 뒤죽박죽(Jumbled) 숫자인지 판별하는 방법입니다.

여기서 뒤죽박죽 숫자란, 모든 자릿수에 대해 인접한 자릿수와의 차이가 최대 1 이하인 수를 의미합니다. 예를 들어 1223은 각 인접 자릿수의 차이가 1 이하이므로 뒤죽박죽 숫자이지만, 1256은 2와 5 사이의 차이가 3으로 1을 초과하므로 뒤죽박죽 숫자가 아닙니다.

문제 해결 접근 방식

이 문제를 해결하려면 숫자의 각 자릿수를 확인하면서, 인접한 자릿수와의 차이가 1보다 큰 경우가 있는지 검사해야 합니다.

• 차이가 1보다 큰 자릿수 쌍이 발견되면 false를 반환합니다.
• 모든 자릿수를 검사했는데도 그런 경우가 없다면 true를 반환합니다.

숫자를 오른쪽부터 한 자릿수씩 처리하기 위해 나눗셈과 나머지 연산을 활용할 수 있습니다. 현재 자릿수는 number % 10으로 구하고, 그 앞자리는 (number / 10) % 10으로 구합니다. 또한 한 자릿수 숫자는 항상 뒤죽박죽 숫자로 간주합니다.

C++ 구현 예제

#include <iostream>
#include <cmath>
using namespace std;

bool isJumbled(int number) {
    if (number / 10 == 0) // 한 자릿수 숫자는 항상 뒤죽박죽 숫자임
        return true;
    while (number != 0) {
        if (number / 10 == 0) // 모든 자릿수 검사를 마치면 true 반환
            return true;
        int curr_digit = number % 10;          // 현재 자릿수
        int prev_digit = (number / 10) % 10;   // 바로 앞 자릿수
        if (abs(prev_digit - curr_digit) > 1)
            return false;
        number = number / 10;
    }
    return true;
}

int main() {
    int n = 1223;
    if(isJumbled(n)){
        cout << n << " is Jumbled";
    } else {
        cout << n << " is not Jumbled";
    }
}

실행 결과

1223 is Jumbled

동작 원리 정리

위 코드는 다음과 같은 단계로 동작합니다.

1. 입력된 숫자가 한 자릿수인지 먼저 확인하고, 맞다면 즉시 true를 반환합니다.
2. 반복문 안에서 현재 자릿수와 그 앞 자릿수를 추출합니다.
3. 두 자릿수의 차이를 abs() 함수로 절댓값을 구해 비교하고, 차이가 1을 초과하면 false를 반환합니다.
4. 숫자를 10으로 나누어 다음 자릿수 쌍을 검사합니다.
5. 모든 자릿수를 통과하면 해당 숫자는 뒤죽박죽 숫자이므로 true를 반환합니다.

이 알고리즘의 시간 복잡도는 숫자의 자릿수에 비례하므로 O(log₁₀ n)이며, 추가 메모리 사용 없이 효율적으로 판별할 수 있습니다.