C++로 n 이하에서 가장 가까운 정돈된 수(Tidy Number) 찾는 방법

어떤 수 n이 주어졌을 때, n보다 작거나 같은 수 중에서 가장 가까운 정돈된 수(Tidy Number)를 찾아야 합니다. 여기서 정돈된 수란 모든 자릿수가 내림차순이 아닌 오름차순(비감소 순서)으로 정렬되어 있는 수를 의미합니다.

예를 들어 입력값이 45000이라면, 각 자릿수가 4 → 5 → 0 → 0 → 0 순서이므로 5 뒤에 0이 오면서 조건을 위반합니다. 따라서 45000보다 작거나 같으면서 가장 가까운 정돈된 수는 44999(4 → 4 → 9 → 9 → 9)가 됩니다.

해결 접근 방식

이 문제는 숫자를 뒤에서부터(오른쪽에서 왼쪽으로) 탐색하면 효율적으로 해결할 수 있습니다. 탐색 과정은 다음과 같습니다.

1. 문자열의 끝에서 두 번째 자릿수부터 시작하여 앞쪽으로 이동합니다.
2. 현재 자릿수가 바로 뒤의 자릿수보다 크면 정돈된 수의 성질이 깨진 것입니다.
3. 이 경우 해당 자릿수를 1 감소시키고, 그 뒤에 있는 모든 자릿수를 전부 '9'로 바꿉니다.
4. 탐색이 끝난 후 결과 문자열을 반환합니다.

이렇게 하면 항상 n보다 작거나 같은 수 중에서 가장 큰 정돈된 수를 얻을 수 있습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

string tidyNum(string number) {
   for (int i = number.length() - 2; i >= 0; i--) {
      if (number[i] > number[i+1]) {
         number[i]--;
         for (int j = i + 1; j < number.length(); j++)
            number[j] = '9';
      }
   }
   return number;
}

int main() {
   string str = "45000";
   string num = tidyNum(str);
   cout << "정돈된 수: " << num;
}

실행 결과

정돈된 수: 44999

동작 원리 상세 설명

입력 "45000"을 기준으로 알고리즘의 진행 과정을 살펴보겠습니다.

- 인덱스 3(숫자 '0')과 인덱스 4(숫자 '0')를 비교: '0' ≤ '0'이므로 통과
- 인덱스 2(숫자 '0')와 인덱스 3(숫자 '0')을 비교: '0' ≤ '0'이므로 통과
- 인덱스 1(숫자 '5')과 인덱스 2(숫자 '0')를 비교: '5' > '0'이므로 위반 → '5'를 '4'로 감소하고 뒤의 자릿수들을 모두 '9'로 변경 → "44000"
- 인덱스 0(숫자 '4')과 인덱스 1(숫자 '4')을 비교: '4' ≤ '4'이므로 통과

최종적으로 "44999"가 출력됩니다.

시간 복잡도

자릿수 개수를 d라고 할 때, 외부 루프가 O(d), 내부 루프 역시 최악의 경우 O(d)이므로 전체 시간 복잡도는 O(d²)입니다. 다만 실제로는 대부분의 경우 한 번의 수정만 발생하므로 사실상 O(d)에 가깝게 동작하며, 공간 복잡도는 입력 문자열 그대로 사용하므로 O(1)의 추가 공간만 필요합니다.