C++로 주어진 숫자에서 반복되는 자릿수 제거하기

이 글에서는 하나의 숫자 n이 주어졌을 때, 그 숫자 안에서 연속으로 반복되는 자릿수를 제거하는 방법을 다룹니다.

입력: x = 12224
출력: 124

입력: x = 124422
출력: 1242

입력: x = 11332
출력: 132

위 예시에서 볼 수 있듯이, 인접한 자릿수가 서로 같으면 하나만 남기고 나머지는 제거하여 새로운 숫자를 만듭니다. 이제 문제 해결 접근 방식과 C++ 구현 코드를 살펴보겠습니다.

문제 해결 접근 방식

핵심 아이디어는 숫자 n의 자릿수를 오른쪽에서 왼쪽으로 하나씩 확인하는 것입니다. 구체적인 과정은 다음과 같습니다.

n을 10으로 나눈 나머지(n % 10)를 구하면 가장 오른쪽 자릿수가 되고, n을 10으로 나누면(n /= 10) 그 자릿수가 제거됩니다. 현재 자릿수(curr)를 바로 앞에서 처리한 자릿수(prev)와 비교하여, 두 값이 같다면 해당 자릿수는 건너뜁니다. 두 값이 다르다면 현재 자릿수를 새로 만들 숫자(new_n)에 추가하고, prev 값을 curr로 갱신한 뒤 루프를 계속 진행합니다.

C++ 구현 코드

#include <bits/stdc++.h>

#define MOD 1000000007

using namespace std;

int main() {
    int n = 1222333232; // 입력 숫자
    int new_n = 0; // 새로 만들어질 숫자
    int po = 1; // 새 자릿수를 더할 때 사용할 10의 거듭제곱
    int prev = -1; // 이전 자릿수
    int curr; // 현재 자릿수
    while(n) {
        curr = n % 10;
        if(prev != curr) { // 중복되지 않은 자릿수인 경우에만 실행
            new_n = new_n + (curr * po); // 새 자릿수를 new_n에 추가
            po *= 10;
            prev = curr;
        }
        n /= 10;
    }
    cout << new_n << "\n";
    return 0;
}

실행 결과

123232

코드 설명

위 코드는 숫자 n의 각 자릿수를 차례대로 순회하면서, 이전 자릿수(prev)와 현재 자릿수(curr)가 일치하지 않을 때만 해당 자릿수를 새 숫자 new_n에 추가합니다. 자릿수를 추가할 때마다 po(10의 거듭제곱)를 곱해 올바른 자릿값 위치에 배치하고, po를 10배씩 늘려 다음 자릿수가 한 칸씩 왼쪽으로 이동하도록 합니다. 만약 현재 자릿수와 이전 자릿수가 같다면 if 블록을 건너뛰고, n이 0이 될 때까지 루프를 계속 반복합니다.

이 알고리즘은 숫자의 모든 자릿수를 한 번씩만 확인하므로 시간 복잡도는 O(d)(d는 자릿수의 개수)이며, 공간 복잡도 역시 O(1)로 매우 효율적입니다.

마무리

이 글에서는 주어진 숫자에서 연속으로 반복되는 자릿수를 제거하는 문제를 해결했습니다. 오른쪽부터 왼쪽으로 자릿수를 탐색하며 인접한 중복을 걸러내는 간단하면서도 효율적인 접근 방식을 배웠습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.