Sum of Digits

Q: 숫자의 각 자릿수를 더하는 시간 복잡도는 얼마인가요?

숫자 하나당 한 단계이므로 O(d) 이며, 여기서 d 는 자릿수입니다. 숫자 n 은 약 log10(n) + 1 개의 자릿수를 가지므로, 같은 상한을 O(log n) 으로 쓰는 경우가 많습니다. 32비트 정수의 경우 최대 10단계입니다.

Q: 숫자로 변환하지 않고 숫자의 각 자릿수를 어떻게 구할까요?

나머지와 10으로 나누는 정수 나눗셈을 사용하세요. n % 10 은 마지막 숫자이고, 나머지를 버리고 n 을 10으로 나누면 그 숫자가 제거됩니다. n 이 0이 될 때까지 반복하면 오른쪽에서 왼쪽으로 모든 숫자를 확인하게 됩니다.

Q: 숫자의 디지털 루트란 무엇인가요?

숫자를 반복해서 더해 한 자리 숫자만 남을 때까지 계산한 결과입니다. 9045 는 18이 되고, 다시 9가 됩니다. 양수 n 의 경우 1 + (n-1) % 9 와 같으며, 모든 수는 자릿수의 합과 9로 나눌 때 같은 나머지를 갖기 때문입니다.

Q: 문자열 버전과 산술 버전 중 어느 쪽이 더 나은가요?

둘 다 O(d) 이며 둘 다 올바릅니다. 문자열 버전은 여러 언어에서 더 짧게 작성할 수 있지만 숫자의 복사본을 만듭니다. 산술 버전은 추가 메모리를 O(1) 사용하며, % 10 과 / 10 이 숫자를 어떻게 분해하는지 알고 있음을 면접관에게 보여 줍니다. 이 내용은 회문 및 숫자 뒤집기 문제에서 다시 등장합니다.

입문수학과 시뮬레이션

+10

음이 아닌 정수 n이 주어집니다. 그 십진수 자릿수의 합을 반환하세요. 예를 들어, 482의 자릿수는 4, 8, 2이므로 답은 14입니다.

함수

sumOfDigits(n: integer) → integer

ninteger: 자릿수를 더하는 음이 아닌 정수
반환값integer: n의 십진수 자릿수의 합

제약 조건

0 ≤ n ≤ 2³¹-1

예제

입력: n = 9045
출력: 18
설명: 9045의 숫자는 9, 0, 4, 5이며, 9 + 0 + 4 + 5 = 18입니다. 0은 아무것도 더하지 않지만 여전히 숫자 하나로 셉니다.

입력: n = 7
출력: 7
설명: 한 자리 수의 각 자릿수의 합은 그 수 자체이므로, 7은 7을 반환합니다.

제출 시 숨은 테스트 +15개

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

숫자는 각 자릿수를 하나씩 알려주지 않으므로, 직접 분해해야 합니다. 숫자를 텍스트로 바꿔 문자를 읽거나, 마지막 자릿수를 분리하는 두 가지 산술 연산을 사용할 수 있습니다. n % 10은 마지막 자릿수를 구하고, 10으로 정수 나눗셈을 하면 마지막 자릿수가 제거됩니다. 두 방법 모두 자릿수마다 한 단계씩 수행하며, 아래에서는 이를 d로 표기하고, 여기서는 d ≤ 10입니다. 산술 연산을 사용하는 방법은 추가 메모리가 필요하지 않습니다.

숫자를 텍스트로 읽기

핵심 아이디어

숫자를 적으면 이미 그 숫자의 자릿수를 볼 수 있습니다. n을 10진수 텍스트로 바꾸면 9045는 네 개의 문자 9, 0, 4, 5가 되고, 그런 다음 문자들을 순회하며 각 문자의 값을 더합니다.

문자는 아직 숫자가 아닙니다. 문자 '4'는 코드 52로 저장되므로, 파싱하거나 '0'의 코드를 빼면 됩니다. '4' - '0' = 4. 숫자 문자의 코드는 연속되어 있으므로, 이 뺄셈은 10개 숫자 모두에 적용됩니다.

텍스트에는 숫자마다 하나씩 d개의 문자가 있으므로, 루프는 O(d) 시간이 걸리고 텍스트 자체는 O(d)의 추가 공간을 사용합니다.

알고리즘

n을 10진수 텍스트로 변환합니다.
total = 0으로 설정합니다.
각 문자의 숫자 값을 total에 더합니다.
total을 반환합니다.

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

% 10을 사용해 마지막 숫자를 떼어 냅니다

핵심 아이디어

문자열 없이도 숫자를 분해할 수 있습니다. 10으로 나눈 나머지는 마지막 자리 숫자입니다: 9045 % 10 = 5. 10으로 정수 나눗셈을 하면 해당 숫자가 버려집니다: 소수 부분을 버리면 9045 / 10 = 904입니다. 이 과정을 반복하면 숫자들이 오른쪽에서 왼쪽으로 나옵니다.

9045의 경우: 5를 더하고 904를 남기고, 4를 더하고 90을 남기고, 0을 더하고 9를 남기고, 9를 더하고 0을 남깁니다. 반복문은 합계가 18인 상태로 0에서 멈춥니다. n = 0이면 반복문이 실행되지 않고 답은 0이며, 이는 올바릅니다.

각 단계에서 숫자 하나가 제거되므로 단계 수는 d이고, 시간 복잡도는 O(d)이며, 메모리에는 정수 두 개만 존재하므로 공간 복잡도는 O(1)입니다. 모든 중간 값은 n보다 작으므로 오버플로가 발생할 수 없습니다.

알고리즘

total = 0으로 설정합니다.
n > 0인 동안 n % 10을 total에 더합니다.
n을 10으로 나누고 소수 부분은 버립니다.
n이 0이 되면 total을 반환합니다.

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

함정과 경계 사례

루프는 짧지만, 실수는 타입과 가장 작은 입력값과 관련이 있습니다.

언어에서 실수 나눗셈을 의미하는 경우 /를 사용하는 것. JavaScript, TypeScript, Lua, PHP 및 R에서 9045 / 10은 904.5이므로 루프에서 소수 부분도 더하게 됩니다. Math.floor 또는 math.floor로 내림하세요. Python에서는 //, Dart에서는 ~/, PHP에서는 intdiv, R에서는 %/%를 사용하세요.
숫자 대신 문자를 더하는 것. 문자 '7'의 코드는 7이 아니라 55입니다. '0'을 빼거나 먼저 문자를 파싱하세요.
n >= 10인 동안 반복하는 것. 그러면 선행 숫자가 여전히 n에 남은 상태로 루프가 끝나 그 숫자는 더해지지 않으므로, 9045의 결과가 18이 아니라 9가 됩니다. n > 0인 동안 반복하세요. 이 조건은 n = 0일 때도 0을 반환합니다.
R에서 큰 수를 텍스트로 출력하는 것. as.character(100000)은 숫자의 여섯 자릿수가 아니라 "1e+05"를 반환합니다. format(n, scientific = FALSE)를 사용하세요.

자주 묻는 질문4

숫자의 각 자릿수를 더하는 시간 복잡도는 얼마인가요?

숫자 하나당 한 단계이므로 O(d)이며, 여기서 d는 자릿수입니다. 숫자 n은 약 log10(n) + 1개의 자릿수를 가지므로, 같은 상한을 O(log n)으로 쓰는 경우가 많습니다. 32비트 정수의 경우 최대 10단계입니다.

숫자로 변환하지 않고 숫자의 각 자릿수를 어떻게 구할까요?

나머지와 10으로 나누는 정수 나눗셈을 사용하세요. n % 10은 마지막 숫자이고, 나머지를 버리고 n을 10으로 나누면 그 숫자가 제거됩니다. n이 0이 될 때까지 반복하면 오른쪽에서 왼쪽으로 모든 숫자를 확인하게 됩니다.

숫자의 디지털 루트란 무엇인가요?

숫자를 반복해서 더해 한 자리 숫자만 남을 때까지 계산한 결과입니다. 9045는 18이 되고, 다시 9가 됩니다. 양수 n의 경우 1 + (n-1) % 9와 같으며, 모든 수는 자릿수의 합과 9로 나눌 때 같은 나머지를 갖기 때문입니다.

문자열 버전과 산술 버전 중 어느 쪽이 더 나은가요?

둘 다 O(d)이며 둘 다 올바릅니다. 문자열 버전은 여러 언어에서 더 짧게 작성할 수 있지만 숫자의 복사본을 만듭니다. 산술 버전은 추가 메모리를 O(1) 사용하며, % 10과 / 10이 숫자를 어떻게 분해하는지 알고 있음을 면접관에게 보여 줍니다. 이 내용은 회문 및 숫자 뒤집기 문제에서 다시 등장합니다.

Python

def sumOfDigits(n):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

n = 9045

기대값