Count Digits

Q: 숫자의 개수를 세는 시간 복잡도는 얼마인가요?

숫자 n 은 floor(log10(n)) + 1 개의 자릿수를 가지며, 루프는 자릿수마다 나눗셈을 한 번 수행하므로 O(log n) 시간과 O(1) 공간이 필요합니다. 32비트 정수의 경우 최대 10단계입니다.

Q: log10을 사용해 숫자의 자릿수를 셀 수 있나요?

양수 n 의 자릿수는 floor(log10(n)) + 1 이지만, 로그는 부동소수점으로 계산됩니다. 0에서는 정의되지 않으며, 10의 거듭제곱에 가까우면 반올림 방향이 잘못될 수 있습니다. 예를 들어 log10(10^15-1) 은 배정밀도에서 정확히 15로 계산됩니다. 정수 나눗셈은 항상 정확합니다.

Q: 음수의 자릿수는 어떻게 세나요?

먼저 절댓값을 구한 다음, 평소처럼 세세요. String(-42) 는 마이너스 기호가 숫자가 아니므로 문자가 세 개입니다. 가장 작은 32비트 정수의 경우 32비트에는 들어가지 않으므로 64비트 타입에서 절댓값을 구하세요.

입문수학과 시뮬레이션

+10

음이 아닌 정수 n이 주어졌을 때, 앞에 0을 붙이지 않고 10진법으로 썼을 때의 자릿수를 반환하세요. 0은 0 하나로 쓰므로 자릿수가 하나입니다.

함수

countDigits(n: integer) → integer

ninteger: 측정할 음이 아닌 정수
반환값integer: n의 소수 자릿수

제약 조건

0 ≤ n ≤ 2³¹-1

예제

입력: n = 4096
출력: 4
설명: 10으로 정수 나눗셈을 하면 4096은 409, 40, 4가 됩니다. 숫자 세 자리가 제거되고 하나가 남으므로 답은 4입니다.

입력: n = 0
출력: 1
설명: 0은 한 자리 숫자로 쓰입니다. 숫자가 0보다 큰 동안 세는 루프는 여기서 실행되지 않으므로 1 대신 0을 반환합니다.

입력: n = 100
출력: 3
설명: 0도 숫자입니다. 100은 1, 0, 0으로 쓰므로 답은 3입니다.

후속 질문

예를 들어 10의 거듭제곱을 이진 탐색하는 방식으로, 각 자릿수마다 한 번씩 실행되는 루프 없이 숫자의 자릿수를 셀 수 있을까요?

힌트

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

3개 중 0개 열림

풀이

10으로 나눌 때마다 숫자가 하나씩 줄어듭니다. 한 자리만 남을 때까지 나눈 횟수를 세고, 그 숫자에 1을 더하세요. 버그는 경계에서 발생합니다. 0은 한 자리이며, 로그 공식은 0과 큰 10의 거듭제곱보다 조금 작은 값에서 실패합니다.

숫자를 텍스트로 쓰고 문자의 수를 세세요

핵심 아이디어

사용 중인 언어는 이미 n을 십진수로 씁니다. 그 문자열을 요청하고 문자의 개수를 세세요. 4096은 "4096"이 되어 문자 4개이고, 0은 "0"이 되므로 0에 대한 특별 처리가 필요하지 않습니다.

변환 과정에서는 각 자릿수마다 나눗셈을 한 번씩 수행하므로 시간과 추가 메모리는 모두 O(log n)이며, 여기서는 최대 10자입니다.

알고리즘

n을 과학적 표기법으로 전환되지 않는 함수를 사용해 십진수 문자열로 변환합니다.
문자열의 문자 수를 셉니다.
그 개수를 반환합니다. 0의 문자열은 "0"이므로 추가 검사 없이 답은 1입니다.

def countDigits(n):
    return len(str(n))

한 자리만 남을 때까지 10으로 나누세요

핵심 아이디어

개수를 1에서 시작하고 n ≥ 10인 동안 10으로 나누며, 나눌 때마다 1을 더합니다. 1에서 시작하면 모든 숫자에 자릿수가 최소 하나 있다는 뜻이며, 이는 0에도 그대로 적용되는 규칙이므로 별도의 확인은 필요하지 않습니다.

2147483647의 경우 루프는 최대 9회 실행됩니다. 시간 복잡도는 O(log n)입니다. 카운터 하나를 유지하고 n의 복사본을 변경하므로 추가 공간 복잡도는 O(1)입니다.

알고리즘

항상 있는 숫자를 위해 count = 1로 설정합니다.
n ≥ 10인 동안 정수 나눗셈으로 n을 10으로 나누고 count에 1을 더합니다.
숫자가 하나 남으면 count를 반환합니다.

def countDigits(n):
    count = 1  # every number, 0 included, has at least one digit
    while n >= 10:
        n //= 10
        count += 1
    return count

함정과 경계 사례

n > 0인 동안 0부터 세는 방법입니다. n = 0이면 0을 반환합니다.
floor(log10(n)) + 1을 사용하는 방법입니다. 0에서는 로그값이 음의 무한대이므로 실패하고, 10^15-1에서는 배정밀도 반올림으로 로그값이 정확히 15가 되어 공식이 자릿수를 16으로 계산합니다.
JavaScript, Lua, PHP 또는 R에서 실수 나눗셈을 사용하면 /는 소수 부분을 유지합니다. 그러면 n > 0인 동안 실행되는 루프는 4096에 대해 328번 실행됩니다. Math.floor, math.floor, intdiv 또는 %/%를 사용하세요.
문자열 버전에서 과학적 표기법을 사용하는 경우입니다. R은 as.character(1e5)를 "1e+05"로 기록합니다. sprintf("%.0f", n)을 사용하세요. Lua 5.3 이상에서는 tostring(4096.0)에 .0이 남으므로 string.format("%d", n)을 사용하세요.

자주 묻는 질문3

숫자의 개수를 세는 시간 복잡도는 얼마인가요?

숫자 n은 floor(log10(n)) + 1개의 자릿수를 가지며, 루프는 자릿수마다 나눗셈을 한 번 수행하므로 O(log n) 시간과 O(1) 공간이 필요합니다. 32비트 정수의 경우 최대 10단계입니다.

log10을 사용해 숫자의 자릿수를 셀 수 있나요?

양수 n의 자릿수는 floor(log10(n)) + 1이지만, 로그는 부동소수점으로 계산됩니다. 0에서는 정의되지 않으며, 10의 거듭제곱에 가까우면 반올림 방향이 잘못될 수 있습니다. 예를 들어 log10(10^15-1)은 배정밀도에서 정확히 15로 계산됩니다. 정수 나눗셈은 항상 정확합니다.

음수의 자릿수는 어떻게 세나요?

먼저 절댓값을 구한 다음, 평소처럼 세세요. String(-42)는 마이너스 기호가 숫자가 아니므로 문자가 세 개입니다. 가장 작은 32비트 정수의 경우 32비트에는 들어가지 않으므로 64비트 타입에서 절댓값을 구하세요.

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

테스트 #1

테스트 #2

테스트 #3

인자

n = 4096

예상 출력