C++로 N보다 크면서 A와 B의 개수가 같은 가장 작은 수 찾기

N, A, B 세 값이 주어졌을 때, N보다 크면서 숫자 A와 B가 정확히 같은 개수만큼 포함된 수를 찾는 문제입니다. 먼저 예시를 살펴보겠습니다.

N = 1234
A = 2
B = 3

이 예시의 정답은 2233입니다. 2233은 1234보다 크고, 숫자 2와 3이 각각 두 번씩 등장하므로 두 숫자의 개수가 동일하기 때문입니다.

이 문제는 가능한 모든 자릿수 조합을 확인해야 합니다. 수를 구성할 수 있는 숫자는 A와 B 두 가지뿐이며, 완성된 수 안에서 각 숫자의 등장 횟수는 반드시 같아야 합니다.

알고리즘

A, B, N을 초기화합니다.
재귀 함수를 작성합니다.
- 현재까지 만든 수가 N 이상이면서 A와 B의 개수가 같은지 확인합니다.
- 조건을 만족하면 그 수를 반환합니다.
- 결과 뒤에 자릿수 A를 붙여 다시 탐색합니다.
- 결과 뒤에 자릿수 B를 붙여 다시 탐색합니다.
- 두 경우 중 더 작은 값을 선택해 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
long getNextGreaterElement(long result, int A, int A_Count, int B, int B_Count, int N) {
    if (result > 1e11) {
        return 1e11;
    }
    if (A_Count == B_Count && result >= N) {
        return result;
    }
    return min(getNextGreaterElement(result * 10 + A, A, A_Count + 1, B, B_Count, N),
        getNextGreaterElement(result * 10 + B, A, A_Count, B, B_Count + 1, N));
}
int main() {
    int N = 1234;
    int A = 2;
    int B = 3;
    cout << getNextGreaterElement(0, A, 0, B, 0, N) << endl;
    return 0;
}

동작 원리

재귀 함수는 현재 수 뒤에 A 또는 B를 하나씩 붙여가며 모든 후보를 체계적으로 탐색합니다. A_Count와 B_Count는 각각 지금까지 사용된 A와 B의 개수를 추적하며, 두 값이 같아지고 동시에 수가 N 이상이 되는 순간 그 수가 유효한 후보가 됩니다. A를 붙인 경우와 B를 붙인 경우 중 항상 더 작은 값을 골라 올라오기 때문에, 최종적으로 조건을 만족하는 가장 작은 수가 반환됩니다. 한편 result > 1e11 조건은 지나치게 큰 수가 만들어지는 상황을 차단하여 무한 재귀를 방지하는 안전장치 역할을 합니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.