[백준] 14912번 숫자 빈도수

문제

1부터 n까지 차례대로 써 내려갈 때 특정 숫자(digit)의 빈도수를 구하여 출력하는 프로그램을 작성하시오.

예를 들어, n = 11 이고 숫자 1의 빈도수를 구하라고 하면, 1 2 3 4 5 6 7 8 9 10 11 에서 숫자 1은 1에서 한 번, 10에서 한 번, 11에서 두 번 나타나므로 1의 빈도수는 총 4 이다.

입력

자연수 n (1 ≤ n ≤ 100,000)과 한 자리 숫자 d(0~9)가 첫째 줄에 주어진다.

출력

첫째 줄에 빈도수를 출력한다.

 

이 문제는 0부터 9까지 배열에 저장 시킨 다음, 값을 증가시키는 형태다.

#include <bits/stdc++.h>
using namespace std;
int digit[10];
int main(void) {
  int n , f;
  cin >> n >> f;

  for(int i = 1;i<=n;i++) {
    string w = to_string(i);
      for(int j = 0;j<w.length();j++) {
        digit[w[j] - '0']++;
      }
  }

  cout << digit[f];
} 

코드는 이렇다. 1부터 n까지 값을 넣어주고 그 값들을 string으로 바꿔준다. 왜냐하면 11같은 경우를 생각해보면

1이 두번 들어가는데, 이것을 나눠서 계산하기 가장 빠른 방법이라 생각했다.

물론 while문을 사용해서 10으로 나누고 10으로 나눈 나머지를 계산하면 값이 나오지만... 그 방법은 이 문제를 풀때 생각이 나지 않았다. 그래서 string으로 우회한뒤 문제를 풀었다.

그러면 string으로 전달된 것이 2자리면 0,1이 들어올것이며 3자리면 0,1,2가 들어온다.

 

그런다음 digit라는 배열을 사용해서 값을 추가해 주면 된다.

 

그리고 어디의 값을 구했는지 출력해주면 완성이다.

 

#include <cstdio>
int main() {
	int N, D, ans = 0; scanf("%d %d", &N, &D);
	for(int i=1; i<=N; i++){
		int num = i;
		while(num){
			if(num % 10 == D) ans++;
			num /= 10;
		}
	}
	printf("%d\n", ans);
	return 0;
}

여기 보면 내가 언급한 방법이다. 하지만 배열에 저장시키는 방법을 택하지 않고, 값을 증가 시키는 방법을 선택했다.

 

뭐 어찌 되었든 아랫쪽이 공간 복잡도만 따졌을때는 더 우수한듯 싶다.

왜냐하면 어떤 특정 문자나 숫자를 저장시키지않았기 때문이다. ㅎㅎ