[Programmers] #120887 - k의 개수 [Java][C++][Python]

문제 링크

---

1. 아이디어

i ~ j의 정수에 대해 k의 등장 횟수를 구하는 문제로 i ~ j까지 각 수에 대해 10으로 나눈 나머지와 몫을 반복 계산하는 자릿수 탐색으로 k의 등장 횟수를 세면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times D)$	$O(1)$

($N$ = j - i + 1, $D$ = j의 자릿수 $\approx \log_{10} j$)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int i, int j, int k) {
        int ans = 0;
        for (int x = i; x <= j; x++) {
            ans += count(x, k);
        }

        return ans;
    }

    static int count(int x, int k) {
        int cnt = 0;
        while (x > 0) {
            if (x % 10 == k) cnt++;
            x /= 10;
        }

        return cnt;
    }
}

#include <bits/stdc++.h>
using namespace std;

int count(int x, int k) {
    int cnt = 0;
    while (x > 0) {
        if (x % 10 == k) cnt++;
        x /= 10;
    }

    return cnt;
}

int solution(int i, int j, int k) {
    int ans = 0;
    for (int x = i; x <= j; x++) {
        ans += count(x, k);
    }

    return ans;
}

def solution(i, j, k):
    return sum(str(x).count(str(k)) for x in range(i, j + 1))

Python은 그냥 문자열로 변환 후 count로 k의 개수를 셌다.

---