이번 글에서는 양의 정수 하나를 입력받아, 1부터 그 수(n)까지의 모든 양의 정수에 등장하는 숫자 1의 총 개수를 구하는 JavaScript 함수를 작성해 보겠습니다.
여기서 n 자체에 1이 포함되어 있다면 n도 반드시 포함해야 합니다. 최종적으로 함수는 이 개수를 반환하면 됩니다.
문제 이해하기
예를 들어 입력값이 다음과 같다고 가정해 봅시다.
const num = 31;
그렇다면 출력 결과는 다음과 같아야 합니다.
const output = 14;
그 이유는 1부터 31 사이에서 숫자 1이 등장하는 수들이 다음과 같기 때문입니다.
1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 31
각 숫자에 포함된 1을 모두 세어 보면 총 14개가 됩니다. 예를 들어 11은 1이 두 번 등장하므로 2개로 계산됩니다.
효율적인 접근 방식
단순히 1부터 n까지 모든 숫자를 문자열로 변환한 뒤 1을 세는 방법도 있지만, 숫자가 매우 커지면 비효율적입니다. 대신 각 자릿수별로 1이 등장하는 규칙을 활용하면 O(log n) 시간 복잡도로 문제를 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 각 자릿수를 기준으로 왼쪽 부분(leftNum)과 오른쪽 부분(rightNum)으로 나누고, 현재 자릿수 값(di)에 따라 경우를 나누어 계산합니다.
- 현재 자릿수가 0인 경우: 왼쪽 숫자 × 해당 자릿수의 크기만큼 1이 등장합니다.
- 현재 자릿수가 1인 경우: 왼쪽 숫자 × 자릿수 크기 + 오른쪽 숫자 + 1만큼 1이 등장합니다.
- 현재 자릿수가 1보다 큰 경우: (왼쪽 숫자 + 1) × 자릿수 크기만큼 1이 등장합니다.
구현 코드
위 접근 방식을 코드로 구현하면 다음과 같습니다.
const num = 31;
const countOnes = (num = 1) => {
if(num <= 0 ){
return 0
};
let sum = 0
num += '';
let helper = p => {
let leftNum = 0
let rightNum = 0
let di = num[p]
if(p>0){
leftNum = parseInt(num.slice(0,p))
}
if(p+1 < num.length){
rightNum = parseInt(num.slice(p+1))
}
if(di > 1){
sum += (leftNum+1)*(10**(num.length-1-p))
} else if(di == 0){
sum += (leftNum)*(10**(num.length-1-p))
} else{
sum += (leftNum)*(10**(num.length-1-p)) + rightNum + 1
}
}
for(let i =0; i < num.length; i++){
helper(i)
};
return sum;
};
console.log(countOnes(num));코드 설명
- 먼저 num이 0 이하이면 0을 반환합니다.
- 숫자를 문자열로 변환하여 각 자릿수에 접근할 수 있게 합니다.
- helper 함수는 각 자릿수 위치 p를 기준으로 왼쪽 숫자와 오른쪽 숫자를 분리합니다.
- 현재 자릿수 값에 따라 세 가지 경우로 나누어 1의 개수를 누적 합산합니다.
- 모든 자릿수에 대해 helper를 호출한 뒤 최종 합계를 반환합니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
14
결과가 14로 나오는 것을 확인할 수 있습니다. 이 알고리즘은 숫자의 자릿수만큼만 반복하므로, 아주 큰 수에 대해서도 빠르게 동작한다는 장점이 있습니다.