Count Digits
음이 아닌 정수 n을 입력받아, 앞에 0을 붙이지 않고 10진수로 썼을 때 몇 자리인지 반환하는 함수를 작성하세요. 0은 0 한 자리로 쓰므로 자릿수는 1입니다.
함수
- ninteger
- 측정할 음이 아닌 정수
- 반환값integer
- n의 소수 자릿수
제약 조건
0 ≤ n ≤ 231-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입니다.
제출 시 숨은 테스트 +16개
후속 질문
예를 들어 10의 거듭제곱을 이진 탐색하는 방식으로, 각 자릿수마다 한 번씩 실행되는 루프 없이 숫자의 자릿수를 셀 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
어떤 수를 10으로 나누고 나머지를 버리면 자릿수는 어떻게 될까요?
10으로 정수 나눗셈을 할 때마다 끝에서 숫자 하나가 정확히 제거됩니다. 한 자리 숫자가 될 때까지 몇 번 나누는지 세어 보세요.
카운터를 1에서 시작하고, 숫자가 10 이상인 동안 10으로 나누면서 매번 1을 더합니다. 1에서 시작하면
0에 대해서도 올바른 답을 얻습니다.
풀이
자릿수는 한 자리만 남을 때까지 10으로 나눌 수 있는 횟수에 그 한 자리를 더한 값입니다. 핵심 아이디어는 한 줄로 설명할 수 있지만, 세부 작업은 예외적인 경우에 있습니다. 0은 자릿수가 하나이고, 자릿수는 9와 10 사이에서 바뀝니다. 로그를 기반으로 한 공식은 0에서 오류가 나며, 부동 소수점 연산에서는 큰 10의 거듭제곱보다 약간 작은 값에서도 오류가 납니다.
숫자를 텍스트로 작성하고 문자 수를 세세요
핵심 아이디어
사용 중인 언어는 이미 n을 10진수로 쓰는 방법을 알고 있습니다. 해당 문자열을 가져와 문자의 개수를 세어 보세요. 4096은 "4096"이 되어 네 문자입니다. 0은 "0"이 되어 한 문자이므로, 0에는 특별한 경우 처리가 필요하지 않습니다.
변환은 라이브러리 내부에서 숫자마다 한 번씩 10으로 나누므로, 작업량은 O(log n)입니다. 문자열에는 숫자마다 문자 하나가 들어가므로, 추가 메모리는 O(log n)이며 여기서는 최대 10자입니다.
형식은 일반적인 10진수여야 합니다. R에서 as.character(1e5)는 "1e+05"를 반환하는데, 여섯 자리 숫자가 다섯 문자가 되므로 sprintf("%.0f", n)을 사용해 형식을 지정하세요. Lua 5.3 이상에서는 tostring(4096.0)이 .0을 유지하지만, string.format("%d", n)은 모든 버전에서 정수를 출력합니다.
알고리즘
n을 과학적 표기법으로 전환하지 않는 함수를 사용해 10진수 문자열로 변환합니다.- 문자열의 문자 수를 셉니다.
- 그 개수를 반환합니다.
0의 문자열은"0"이므로 추가 검사 없이 답은1입니다.
def countDigits(n):
return len(str(n))한 자리만 남을 때까지 10으로 나누세요
핵심 아이디어
정수 나눗셈으로 10으로 나누면 마지막 자릿수가 사라집니다. 4096 / 10은 409입니다. 나눗셈을 한 번 할 때마다 자릿수가 하나씩 줄어들므로, 한 자리 수가 될 때까지 나눈 횟수에 마지막 자릿수 몫으로 1을 더하면 답이 됩니다. 4096은 세 번 나눠야 하므로 (409, 40, 4), 자릿수는 4개입니다.
개수를 1에서 시작하고 n ≥ 10인 동안 나눕니다. 1에서 시작한다는 것은 모든 수에 자릿수가 최소 하나는 있다는 뜻이며, 이는 0에 대한 규칙과 정확히 일치합니다. 처음에 흔히 작성하는 방식처럼 0에서 시작해 n > 0인 동안 세면 n = 0일 때 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의 거듭제곱보다 약간 작은 큰 값에서도 실패합니다. 배정밀도에서는log10(10^15-1)이 반올림되어 정확히15가 되므로, 이 공식은 15자리가 아니라 16자리라고 합니다.n > 0인 동안 실행되는 루프에서 실수 나눗셈 사용하기. JavaScript, Lua, PHP, R에서는/가 소수 부분을 유지하므로,4096은 0에 도달하기까지 328단계 동안 0에 가까워집니다.Math.floor,math.floor,intdiv또는%/%를 사용하세요.- 문자열 변환 버전에서 과학적 표기법 사용하기: R은
100000을"1e+05"로 씁니다. - 빼기 기호를 숫자로 세기. 여기서 입력값은 음수가 아니지만,
String(-42)에는 문자가 세 개 있으므로 음수를 처리하는 버전에서는 먼저 절댓값을 취합니다.
자주 묻는 질문4
숫자를 문자열로 변환하지 않고 자릿수를 어떻게 세나요?
한 자리만 남을 때까지 정수 나눗셈으로 10으로 나누면서 나눗셈 횟수를 세고, 마지막 자릿수에 1을 더합니다. 4096은 409, 40, 4가 됩니다. 세 번 나눴으므로 자릿수는 4개입니다. 이 루프는 추가 공간 O(1)을 사용합니다.
0은 왜 한 자리 숫자일까요?
0은 0이라는 한 문자로 쓰이므로, 십진수 표기에는 한 자릿수가 있습니다. 숫자가 0보다 큰 동안 나눗셈 횟수를 세는 코드는 0일 때 실행되지 않아 0을 반환합니다. 카운터를 1에서 시작하고 숫자가 10 이상인 동안 나누면 특별한 경우를 처리할 필요가 없습니다.
log10을 사용해 숫자의 자릿수를 셀 수 있나요?
양의 n에 대해서 개수는 floor(log10(n)) + 1이지만, 로그는 부동소수점 방식으로 계산됩니다. 0에서는 정의되지 않으며, 10의 거듭제곱에 가까우면 반올림으로 잘못된 결과가 나올 수 있습니다. 예를 들어 log10(10^15-1)은 배정밀도에서 정확히 15로 계산됩니다. 정수 나눗셈은 매번 정확한 답을 제공합니다.
자릿수를 세는 시간 복잡도는 얼마인가요?
숫자 n은 floor(log10(n)) + 1개의 자릿수를 가지며, 루프는 자릿수마다 한 번씩 나누기를 수행하므로 O(log n) 시간에 실행됩니다. 32비트 정수의 경우 최대 10단계입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def countDigits(n):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
n = 4096
기대값
4