[리트코드 3723] 자릿수 제곱합 최대화 — 큰 숫자부터 채우기

원제: Maximize Sum of Squares of Digits

문제 요약

자릿수가 정확히 num개이고 각 자릿수의 합이 sum인 양의 정수 중, 자릿수 제곱합이 최대인 정수를 문자열로 반환합니다. 점수가 같은 정수가 여러 개라면 그중 가장 큰 정수를 반환하고, 조건을 만족하는 정수가 없으면 ""를 반환합니다.

조건과 입출력

num과 sum은 양의 정수이며, 1 <= num <= 2 * 10^5, 1 <= sum <= 2 * 10^6입니다. 정수의 자릿수는 정확히 num개여야 하고, 자릿수의 합은 정확히 sum이어야 합니다. 한 자릿수는 0부터 9까지이므로 만들 수 있는 최대 합은 num * 9입니다.

예제와 문제 자료

예제 1: num = 2, sum = 3이면 반환값은 "30"입니다. 12와 21의 점수는 5지만 30의 점수는 9입니다. 예제 2: num = 2, sum = 17이면 반환값은 "98"입니다. 89와 98의 점수는 같고, 그중 더 큰 수가 98입니다. 예제 3: num = 1, sum = 10이면 반환값은 ""입니다. 한 자릿수로 합 10을 만들 수 없습니다.

풀이 아이디어

각 자릿수의 합이 고정되어 있을 때 제곱합을 크게 하려면 합을 적은 수의 큰 자릿수에 몰아야 합니다. 예를 들어 두 자릿수의 합이 3이라면 1과 2로 나누는 것보다 3과 0으로 나누는 편이 제곱합이 큽니다. 코드에서는 이를 위해 앞자리부터 가능한 한 9를 넣고, 남은 합을 다음 자리에 넣습니다. 가능한 최대 자릿수 합인 num * 9를 초과하면 만들 수 없으므로 바로 ""를 반환합니다. 이 방식은 같은 점수를 내는 자릿수 배열이 있더라도 큰 자릿수를 앞에 배치하므로 가장 큰 정수를 반환합니다.

코드의 핵심

answer에는 각 자릿수를 순서대로 담습니다. 반복문에서 sum >= 9이면 현재 자리에 9를 넣고 sum -= 9로 남은 합을 줄입니다. 9보다 작으면 남은 합 자체를 현재 자리에 넣고 sum -= sum으로 0으로 만듭니다. 그 뒤 반복에서 남은 자리에 0이 들어가므로 자릿수는 계속 정확히 num개입니다. 마지막에 "".join(map(str,answer))로 숫자 목록을 문자열로 변환합니다.

코드 추적 — 예제 1 (num = 2, sum = 3): 첫 자리에서는 sum >= 9가 거짓이므로 3을 넣고 합을 0으로 만듭니다. 다음 자리는 0이 됩니다. 따라서 answer는 [3, 0]이고 반환값은 "30"입니다.

제출 코드

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        if sum > num * 9:
            return ""

        answer = []
        for i in range(num):
            if sum >= 9:
                answer.append(9)
                sum -= 9
            else:
                answer.append(sum)
                sum -= sum

        return "".join(map(str,answer))

복잡도

num을 자릿수 개수라 하면 반복문은 num회 실행되므로 시간 복잡도는 O(num)입니다. answer가 자릿수마다 원소 하나를 저장하므로 보조 공간은 O(num)이며, 반환 문자열도 O(num) 공간을 사용합니다.

복습 포인트

원문에서 sum은 양수이므로 sum > num * 9만 불가능 조건으로 검사해도 됩니다. sum == num * 9인 경우에는 모든 자리에 9가 들어갑니다. 반환 타입이 정수가 아니라 문자열이라는 점에 유의하세요.

출처

문제 원문