파이썬으로 n 이하의 수 중 모든 자릿수가 감소하지 않는 가장 큰 수 찾기

문제 소개

숫자 n이 주어졌을 때, n보다 작거나 같은 수 중에서 모든 자릿수가 감소하지 않는(왼쪽에서 오른쪽으로 갈수록 같거나 커지는) 가장 큰 수를 찾아야 합니다.

예를 들어 입력이 n = 221이라면 출력은 199입니다. 221은 마지막에 2 → 1로 자릿수가 줄어드는 부분이 있지만, 199는 1 ≤ 9 ≤ 9 조건을 만족하기 때문입니다.

해결 접근 방법

이 문제는 숫자를 뒤에서부터 검사하면서 자릿수가 어긋나는 지점을 찾는 방식으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.

1. n의 모든 자릿수를 리스트(digits)로 변환합니다.
2. 경계 위치를 저장할 변수 bound를 초기화합니다.
3. 마지막 자릿수부터 두 번째 자릿수까지 역순으로 반복하며 검사합니다.
4. 현재 자릿수가 바로 앞 자릿수보다 작으면 bound에 해당 인덱스를 기록하고 앞 자릿수를 1 감소시킵니다.
5. bound가 설정된 경우, bound 위치부터 끝까지의 모든 자릿수를 9로 채웁니다.
6. 모든 자릿수를 이어 붙여 하나의 정수로 만든 뒤 반환합니다.

앞자리를 1 줄였기 때문에 그 뒤의 자릿수를 모두 9로 채워도 결과값은 여전히 n 이하이며, 조건을 만족하는 수 중에서 가장 큰 값이 됩니다.

예제 코드

class Solution:
    def solve(self, n):
        digits = [int(x) for x in str(n)]
        bound = None
        for i in range(len(digits) - 1, 0, -1):
            if digits[i] < digits[i - 1]:
                bound = i
                digits[i - 1] -= 1
        if bound:
            for i in range(bound, len(digits)):
                digits[i] = 9
        return int("".join(map(str, digits)))

ob = Solution()
n = 221
print(ob.solve(n))

입력

221

출력

199

동작 과정 살펴보기

n = 221일 때 코드가 어떻게 동작하는지 단계별로 확인해 보겠습니다.

• 초기 상태: digits = [2, 2, 1]
• 첫 번째 검사(i = 2): 1이 앞자리 2보다 작으므로 bound = 2로 설정하고 앞자리를 1 줄입니다. 이후 bound 위치부터 9로 채워 [2, 1, 9]가 됩니다.
• 두 번째 검사(i = 1): 1이 앞자리 2보다 작으므로 bound = 1로 설정하고 앞자리를 1 줄입니다. 다시 9로 채워 [1, 9, 9]가 됩니다.
• 최종 결과: 199가 반환됩니다.

복잡도 분석

시간 복잡도와 공간 복잡도는 모두 자릿수 개수 d에 비례하여 O(d)입니다. 따라서 숫자가 아무리 커도 자릿수 길이에 선형적인 시간 안에 효율적으로 처리할 수 있습니다.