문제 설명
1부터 13까지의 수에서, 1은 1, 10, 11, 12, 13 이렇게 총 6번 등장합니다. 정수 i, j, k가 매개변수로 주어질 때, i부터 j까지 k가 몇 번 등장하는지 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤
i<j≤ 100,000 - 0 ≤
k≤ 9
입출력 예
| i | j | k | result |
|---|---|---|---|
| 1 | 13 | 1 | 6 |
| 10 | 50 | 5 | 5 |
| 3 | 10 | 2 | 0 |
💡 문제 이해하기 → 접근 방법 → 코드 설계 → 코드 구현
1. 문제 이해하기
시작하는 숫자부터 끝나는 숫자까지 모든 자리수에 정해진 숫자가 몇 번 나타나는지 카운트하는 문제
- 제한사항이 10^5 까지 숫자를 받을 수 있도록 되어 있기 때문에 시간 복잡도가 O(N^2)으로 걸리는 알고리즘을 선택하면 안 될 것 같다. 최소 O(N)으로 풀이해야 한다.
- 반환값은 숫자를 리턴한다.
2. 접근 방법
- 직관적으로 생각하기
- 주어진 숫자를 자리수를 구분해서 각 숫자의 배열로 나누고 배열마다 정해진 숫자가 몇 번 나타나는지 비교해서 하나씩 나타날때마다 카운트를 하나씩 추가한다.
- 하지만 위와 같은 방법으로 풀이하게 되면 이중 for문을 사용해야 할 것 같은데, 그렇게 되면 시간복잡도가 O(N^2)이니까 이 방법은 안되지 않을까라고 생각한다.
3. 코드 설계
일단 i부터 j까지의 숫자만큼 반복해서 for문으로 숫자 하나하나를 배열로 변환한 다음에 각 배열을 다시 for 문으로 돌면서 k와 같은 배열의 요소가 있을 때마다 카운트를 추가한다.
4. 코드 구현
function solution(i, j, k) {
let count = 0
for (let n = i; n <= j; n++) {
const nArr = String(n).split('')
for (let m = 0; m < nArr.length; m++) {
if (nArr[m] === String(k)) {
count++
}
}
}
return count
}다른 사람 풀이
function solution(i, j, k) {
let a ='';
for(i;i<=j;i++){
a += i;
}
return a.split(k).length-1;
}반복을 도는 건 동일하지만 a를 배열로 만들기 전에 모든 숫자를 하나의 문자열에 추가하고 split의 기준을 k로 함으로써 k를 기준으로 나눠진 나머지가 배열에 담기게 되고 그렇게 되면서 k보다 한 개더 많도록 배열에 담기게 되는 최종적으로 length -1을 통해 결과를 도출할 수 있는 코드
function solution(i, j, k) {
let str = Array(j - i + 1).fill(i).map((v, i) => v + i).join('')
return Array.from(str).filter(t => +t === k).length;
}j와 i의 차이 만큼 배열을 생성하고 map과 join을 이용해서 모든 숫자들을 하나의 문자열로 만들고 그 문자열을 하나하나 쪼개서 다시 배열에 담은 다음 filter를 이용해서 k와 같은 만큼만 배열로 만들어서 그 배열의 길이를 구하는 코드
회고
처음에 접근 방법에 대해서 생각할 때 이중 for문을 사용해야 하는 상황이라 무조건 시간 복잡도가 O(N^2)이 걸릴 줄 알았는데, 생각해보니까 처음 N의 경우에는 10^5 이지만 두 번째 for문을 돌때는 자리수만큼 반복문을 돌기 때문에 최대 6번을 넘지 않았다. 그렇기 때문에 최악의 시간복잡도라고 해봤자, 6 x 10^5 이기 때문에 10^8을 넘지 않아서 최종적으로 테스트에 통과할 수 있었다.
다른 사람들의 풀이를 보면서 매번 느끼는 거지만, 알고리즘적인 사고력이 정말 중요하다는 걸 느낀다.
