[Level 0] 숫자 빈도수

문제

두 자연수 M, N을 입력 받아, M부터 N까지 각 자리수의 빈도수를 합하는 프로그램을 제작하시오.
예를 들어 129와 137이 주어졌을 때, 129, 130, 131, 132, 132, 133, 134, 135, 136, 137 숫자가 나오고, 이 숫자들의 자릿수 별 숫자 빈도수를 계산하여, 0부터 9까지의 빈도수 값을 반환한다.
입력 값은 M, N은 10,000 이하의 자연수이며, 0부터 9까지의 자릿수 별 빈도수를 배열 형태로 반환한다.

 

입력 형식

• 1번 예제 : M=129, N=137
• 2번 예제 : M=1412, N=1918
• 3번 예제 : M=4159, N=9182

 

출력 형식

• 1번 예제 : [1, 10, 2, 9, 1, 1, 1, 1, 0, 1]
• 2번 예제 : [100, 614, 101, 101, 189, 201, 201, 201, 201, 119]
• 3번 예제 : [1503, 1527, 1503, 1502, 2343, 2503, 2512, 2512, 2505, 1686]

 

---

내 풀이

function solution(a,b) {
	let result = [];
	for(let i = 0; i < 10; i++) result[i] = 0;

	for(let i = a; i <= b; i++){
		let value = i;
		while(value !== 0){
			result[value % 10] = ++result[value % 10];
			value = Math.floor(value/10);
		}
	}
	return result;
}

console.log(solution(129, 137));
console.log(solution(1412, 1918));
console.log(solution(4159, 9182));

 

• 시간 복잡도 : O((b - a + 1) * k)
• 설명 : 이 코드의 시간 복잡도는 입력 범위에 따라 다르다.
  주어진 범위 a와 b에 따라서 for 루프는 a부터 b까지의 숫자들을 순회하게 된다. 이 for 루프의 반복 횟수는 b - a + 1번이다.
  안쪽의 while 루프는 숫자 value에 대해서 각 자릿수의 등장 횟수를 세는 작업을 수행한다. value의 크기에 따라서 while 루프가 몇 번 반복되는지 결정된다. 가장 최악의 경우는 value가 10의 거듭제곱인 경우이다. 예를 들어, value가 1000이라고 가정하면, while 루프는 4번 반복되게 된다.
  따라서 이 코드의 시간 복잡도는 O((b - a + 1) * k)로 표기할 수 있다. 여기서 k는 입력 범위에 따라 달라지는 상수이다. k는 주어진 숫자의 최대 자릿수에 의해 결정되며, 일반적으로 상수로 취급된다. 즉, k는 상대적으로 작기 때문에 시간 복잡도를 나타낼 때는 무시된다.
  따라서 이 코드는 주어진 범위에 따라 선형 시간에 처리되는 알고리즘이다. 입력 범위가 적당하다면 효율적으로 동작할 것이다. 그러나 입력 범위가 매우 크다면 선형 시간으로도 부담이 될 수 있으니 이점을 고려하여 사용하는 것이 좋다.
• 느낌점 : 나는 이 문제를 풀지 못하고 정답을 봤다. 우선 나는 a와 b의 범위 안에 들어가는 모든 숫자들의 배열을 만들고, 그 배열의 각 요소들을 String으로 만든 후 각 문자열이 어떤 값을 가지고 있는지 for문을 돌려 0~9의 값이 들어있는 map의 value를 증가 시키는 방법을 생각했다. 하지만 이 방법은 반복문 안에서 숫자를 String으로 변환한 뒤 문자열 하나하나씩 탐색해야 하므로 효율적이지 못하다고 생각했고, 다른 방법을 생각하기로 했다. 그러나 다른 방법이 떠오르지 않자, 정답을 봤다. 
  이렇게 몇줄 안 되는 코드로 나타낼 수 있는걸 왜 생각하지 못했는지 이마를 탁 쳤다. 앞으로 이런 알고리즘 문제는 문자열 보다는 최대한 반복문과 연산을 활용해보는 방식으로 접근해야 하는 것을 알았다.

 

---