이 문제에서는 정수 N이 주어지며, 최대 2개의 서로 다른 숫자(고유 숫자)만 사용하여 만들 수 있는 N보다 작은 모든 수를 출력해야 합니다. 즉, 하나의 숫자를 구성할 때 사용할 수 있는 숫자 종류는 최대 2개입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: N = 17
출력: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
N이 17인 경우, 1부터 16까지의 모든 수는 한두 개의 숫자만으로 구성되므로 전부 출력됩니다. 반면 100 같은 수는 1, 0, 0으로 세 개의 숫자가 관련되어 있지만 실제 사용된 고유 숫자는 '1'과 '0' 두 개뿐이므로 포함될 수 있습니다.
접근 방법
이 문제를 해결하는 핵심 아이디어는 두 개의 고유 숫자만으로 구성된 모든 수를 직접 생성하는 것입니다. 수 생성은 0부터 시작하며, 생성된 수가 N보다 크거나 같아지면 더 이상 진행하지 않습니다.
선택된 두 숫자를 i와 j라고 할 때, 재귀적으로 num*10+i와 num*10+j 형태로 새로운 수를 만들어 나갑니다. 이 과정에서 서로 다른 조합이 같은 수를 만들 수 있으므로 중복이 발생하는데, set(집합) 자료구조를 사용하면 중복을 자동으로 제거하고 오름차순 정렬 효과도 얻을 수 있습니다.
알고리즘 동작 원리
- 0부터 9까지의 숫자 중 서로 다른 두 숫자 i, j의 모든 조합을 선택합니다.
- 각 조합에 대해 재귀 함수가 num*10+i와 num*10+j를 호출하며 가능한 모든 수를 생성합니다.
- 생성된 수가 0보다 크고 N보다 작으면 집합에 저장합니다.
- 수가 N보다 크거나 같으면 해당 분기의 탐색을 종료합니다.
- 마지막으로 집합에 저장된 모든 수를 오름차순으로 출력합니다.
예제 코드
다음 프로그램은 위 접근 방식을 C++로 구현한 것입니다.
#include <bits/stdc++.h>
using namespace std;
set<int> numbers;
void generateNumbers(int n, int num, int i, int j){
if (num > 0 && num < n)
numbers.insert(num);
if (num >= n)
return;
if (num*10+i > num)
generateNumbers(n, num*10+i, i, j);
generateNumbers(n, num*10+j, i, j);
}
void printUniqueBitNumber(int n){
for (int i = 0; i <= 9; i++)
for (int j = i + 1; j <= 9; j++)
generateNumbers(n, 0, i, j);
cout<<"The numbers are generated are : ";
while (!numbers.empty()) {
cout<<*numbers.begin()<<" ";
numbers.erase(numbers.begin());
}
}
int main(){
int n = 17;
printUniqueBitNumber(n);
return 0;
}
출력 결과
The numbers are generated are : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
코드 설명
generateNumbers 함수는 현재 수 num이 유효한 범위(0보다 크고 n보다 작음)에 있으면 집합에 삽입한 뒤, num 앞에 숫자 i 또는 j를 붙인 새로운 수를 재귀적으로 생성합니다. num*10+i가 num보다 커지는 경우에만 호출하여 불필요한 무한 재귀를 방지합니다.
printUniqueBitNumber 함수는 가능한 모든 숫자 쌍(i, j)에 대해 수 생성을 수행하고, 집합의 특성 덕분에 이미 정렬된 상태로 저장된 값들을 차례로 출력합니다. 이 방식의 시간 복잡도는 N의 자릿수에 비례하여 생성되는 수의 개수에 의해 결정되므로, N이 클 경우에도 효율적으로 동작합니다.