문제 개요
이 문제에서는 하나의 숫자 n이 주어지며, 우리의 목표는 n보다 작으면서 모든 자릿수가 중복 없이 서로 다른 숫자를 만족하는 가장 큰 수를 찾아 출력하는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: n = 2332
출력: 2319
위 예시에서 2332보다 작은 수 중 자릿수가 모두 다른 가장 큰 수는 2319입니다. (2321은 2가 두 번 나타나므로 조건을 만족하지 않습니다.)
접근 방법
이 문제를 해결하는 가장 직관적인 방법은 n부터 0까지 역순으로 숫자를 검사하는 것입니다. 각 숫자에 대해 다음 과정을 수행합니다.
- 현재 검사 중인 숫자의 각 자릿수를 분리합니다.
- 0~9까지 각 숫자가 몇 번 등장했는지 개수 배열(count)에 기록합니다.
- 총 자릿수와 서로 다른 자릿수의 개수가 일치하면, 해당 숫자는 모든 자릿수가 고유한 것이므로 정답이 됩니다.
- 조건을 만족하는 첫 번째 숫자를 발견하면 즉시 반환하고 탐색을 종료합니다.
역순으로 탐색하기 때문에 처음으로 조건을 만족하는 수가 곧 가장 큰 수이며, 루프의 최대 반복 횟수는 항상 n보다 작습니다.
구현 예제
위 접근 방식을 C++로 구현한 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int findDistinctDigitNumber(int n) {
for (int i = n - 1; i >= 0; i--) {
int count[10] = { 0 };
int x = i;
int count1 = 0, count2 = 0;
// 각 자릿수의 등장 횟수 계산
while (x) {
count[x % 10]++;
x /= 10;
count1++;
}
// 한 번만 등장한 자릿수 개수 세기
for (int j = 0; j < 10; j++) {
if (count[j] == 1)
count2++;
}
// 전체 자릿수와 고유 자릿수가 일치하면 정답
if (count1 == count2)
return i;
}
}
int main() {
int n = 44324;
cout << "Number less than " << n << " with all digits distinct are : " << findDistinctDigitNumber(n);
return 0;
}
실행 결과
Number less than 44324 with all digits distinct are : 43987
동작 설명
입력값이 44324인 경우, 프로그램은 44323부터 시작하여 아래 방향으로 하나씩 검사합니다. 44323에는 4가 여러 번 등장하므로 조건을 만족하지 않고, 탐색을 계속 진행한 결과 43987에서 처음으로 모든 자릿수(4, 3, 9, 8, 7)가 서로 다른 것을 확인하고 해당 값을 반환합니다.
시간 복잡도
각 숫자의 자릿수 검사는 O(d)입니다(여기서 d는 자릿수). 최악의 경우 탐색 범위에 따라 시간이 소요되지만, 실제로는 조건을 만족하는 수가 비교적 가까운 거리에 존재하는 경우가 많아 빠르게 결과를 얻을 수 있습니다.