[자바] 백준 14912 - 숫자 빈도수 (java)

 문제 : boj14912

---

 

필요 알고리즘 개념

• 브루트포스
  
  • 모든 경우의수를 확인해보면 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  최대 n은 10만이고, 최대 자리수는 6개이다. 따라서 1부터 n까지 모든 자리수를 하나씩 비교해보더라도 O(N)이면 되므로 브루트포스로 모든 경우를 확인해주면 된다.

 

  각 자리수를 모두 확인하려면 우선 편한 방법으로는 1부터 n까지 각 수를 String으로 변경해준 뒤 String의 각 character를 순회하면서 카운팅해주면 된다. 다만 String을 만드는건 대부분의 경우 비효율적이다.

 

  더 효율적으로 하려면 이하 코드처럼 int 그대로 각 자리수를 확인해보면 된다. 혹시 어떻게 하는지 모르겠다면 이참에 익혀보자. getCnt 함수에서 num이 현재 보려는 숫자이고, d가 입력으로 주어진 한 자리 숫자이다. 만약 num이 1234라고 해보자.

 

1. num%10은 현재 num의 1의자리수이다. num이 처음에 1234였으므로 '4'에 해당하고, 이게 d인지 비교해준다.

2. num/=10을 해주면 '1'에서 비교했던 수 부분은 사라진다. 즉 각 자리수를 하나씩 우측으로 밀어준게 된다. 결과는 123이다.

3. 다시 num%10은 '3'이니 이게 d인지 비교해준다.

4. num/=10으로 12가 된다.

5. num%10은 '2'이다.

6. num/=10은 1이다.

7. num%10은 '1'이다.

8. num/=10은 0이다. while(num!=0) 이므로 여기서 종료된다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private int getCnt(int num, int d) {
        int cnt = 0;
        while (num!=0) {
            if (num%10 == d)
                cnt++;
            num/=10;
        }
        return cnt;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += getCnt(i, d);
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}