C++에서 숫자가 1, 14, 144의 연결로만 구성되었는지 확인하는 방법

이번 글에서는 주어진 숫자나 문자열이 오직 1, 14, 144만을 이어 붙여 만든 형태인지 판별하는 문제를 다뤄보겠습니다. 예를 들어 "111411441"은 1 · 1 · 14 · 1 · 144 · 1의 연결이므로 유효한 숫자지만, "144414"는 어떤 조합으로도 표현할 수 없기 때문에 유효하지 않습니다.

문제 해결 접근 방식

핵심 아이디어는 매우 간단합니다. 숫자의 마지막 자리부터 세 자리, 두 자리, 한 자리 단위로 잘라 내어 각각 144, 14, 1과 일치하는지 확인합니다. 일치하는 부분을 찾으면 해당 자릿수만큼 숫자를 줄인 뒤 같은 과정을 반복하고, 이를 숫자가 완전히 소진될 때까지 진행합니다. 도중에 세 가지 중 어느 것과도 맞지 않는 부분이 등장하면 그 숫자는 유효하지 않은 것으로 판정합니다.

C++ 구현 예제

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

bool checkNumber(long long number) {
    int n = number;
    while (n > 0) {
        if (n % 1000 == 144)
            n /= 1000;
        else if (n % 100 == 14)
            n /= 100;
        else if (n % 10 == 1)
            n /= 10;
        else {
            return false;
        }
    }
    return true;
}

int main() {
    long long n = 111411441;
    if (checkNumber(n)) {
        cout << "Valid number";
    } else {
        cout << "Invalid number";
    }
}

실행 결과

Valid number

코드 동작 원리

• n % 1000 == 144 : 숫자의 마지막 세 자리가 144인지 검사합니다. 조건이 참이면 1000으로 나누어 해당 세 자리를 제거합니다.
• n % 100 == 14 : 마지막 두 자리가 14인지 검사하고, 참이면 100으로 나눕니다.
• n % 10 == 1 : 마지막 한 자리가 1인지 검사하고, 참이면 10으로 나눕니다.
• 세 조건 모두 만족하지 않으면 즉시 false를 반환합니다.
• 반복문이 종료되어 n이 0이 되었다면 모든 자릿수가 1, 14, 144로 성공적으로 분해된 것이므로 true를 반환합니다.

참고로 위 예제에서는 long long 값을 int 변수에 대입하고 있는데, 매우 큰 수를 다룰 가능성이 있다면 checkNumber 함수 내부에서도 long long 타입을 그대로 사용하는 것이 안전합니다. 이 알고리즘은 숫자를 한 번에 몇 자리씩 줄여 가며 검사하므로 시간 복잡도는 숫자의 자릿수에 비례하며, 따라서 매우 효율적인 편입니다.