음이 아닌 정수 N이 주어졌을 때, N보다 작거나 같으면서 단조 증가(monotone increasing)하는 자릿수를 가진 가장 큰 수를 구하는 것이 이 문제의 목표입니다. 어떤 정수가 단조 증가하는 자릿수를 가진다는 것은, 인접한 두 자릿수 x와 y에 대해 항상 x <= y가 성립한다는 의미입니다. 예를 들어 입력이 332라면 출력은 299가 됩니다.
문제 이해하기
332는 마지막 자리에서 3에서 2로 감소하기 때문에 단조 증가하지 않습니다. 따라서 332 이하의 수 중에서 각 자릿수가 왼쪽에서 오른쪽으로 커지거나 같게 유지되는 가장 큰 수를 찾아야 하며, 그 답은 299입니다.
해결 전략
이 문제는 그리디(greedy) 방식으로 효율적으로 해결할 수 있습니다. 숫자를 문자열로 변환한 뒤, 처음으로 자릿수가 감소하는 지점을 찾고 해당 위치의 자릿수를 하나 줄인 다음, 그 뒤의 모든 자릿수를 9로 채우면 됩니다. 구체적인 단계는 다음과 같습니다.
- N을 문자열 s로 변환하고, i := 1, n := 문자열 s의 길이로 초기화합니다.
- i < n이고 s[i] >= s[i - 1]인 동안 i를 1씩 증가시켜, 처음으로 감소가 발생하는 위치를 찾습니다.
- 감소 지점이 존재한다면(i < n), i > 0이고 s[i - 1] > s[i]인 동안 i를 1 감소시키고 s[i]를 1 감소시킵니다. 이 과정은 자릿수를 줄였을 때 앞자리와의 대소 관계가 깨지는 경우를 연쇄적으로 처리하기 위한 것입니다.
- i + 1부터 n까지의 모든 자릿수를 '9'로 설정합니다.
- 문자열 s를 정수로 변환하여 반환합니다.
다음 구현 예제를 통해 더 잘 이해할 수 있습니다.
예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int monotoneIncreasingDigits(int N) {
string s = to_string(N);
int i = 1;
int n = s.size();
while(i < n && s[i] >= s[i - 1]) i++;
if( i < n)
while(i > 0 && s[i - 1] > s[i]){
i--;
s[i]--;
}
for(int j = i + 1; j < n; j++)s[j] = '9';
return stoi(s);
}
};
main(){
Solution ob;
cout << (ob.monotoneIncreasingDigits(332));
}
입력
332
출력
299
동작 과정 살펴보기
입력 332의 경우를 단계별로 살펴보면 다음과 같습니다.
- 문자열 "332"에서 처음으로 감소가 발생하는 위치는 인덱스 2입니다('3' 다음에 '2'가 옴).
- 앞자리를 조정하는 과정에서 s[1]이 3에서 2로, 이어서 s[0]이 3에서 2로 감소하여 문자열은 "222"가 됩니다.
- 인덱스 1 이후의 모든 자릿수를 9로 채우면 "299"가 되며, 이것이 최종 답입니다.