(Python/파이썬) - 백준(BOJ) 14912번 : 숫자 빈도수

https://www.acmicpc.net/problem/14912

14912번: 숫자 빈도수

---

• 문제 : 

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

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

 

 

 

---

• 풀이 :

구현, 완전탐색 문제입니다. 

 

알고리즘의 흐름입니다.

 

1.  1부터 N까지의 숫자를 탐색합니다. 

 

2.  각 숫자를 a라고 하였을 때, 한 문자단위부터 a의 길이만큼의 문자단위까지 자릅니다.

 

ex ) 1234 라는 숫자일 때  

 

1자리 -> 1, 2, 3, 4

2자리 -> 12, 23, 34

3자리 -> 123, 234

4자리 -> 1234

 

 

3.  가공한 숫자가 문자열로 변환한 D (문제에서 요구하는 숫자)와 같다면 정답 카운트를 1 증가시킵니다.

 

 

주의할 점) 가공한 숫자와 주어진 를 비교할 때 D를 문자열료 변환해서 비교해야 합니다.  그 이유는

 

101 이라는 숫자가 들어왔을 때 D가 1이라면

 

1 자리 -> 1, 0, 1

2 자리 -> 10, 01

3 자리 -> 101

 

이렇게 나누어집니다. 이게 s값의 후보들인데 정답은 2가 됩니다. 그러나 s를 int로 변경하여 비교할 경우 2자리의 01은 1로 변환되어 정답이 3으로 나오게 됩니다. 따라서 주어진 숫자 D를 문자열로 변환하여 비교해야 합니다.

 

 

아이디어) 처음에는 1부터 N까지의 배열을 만들어 각 자릿수를 모두 카운트하는 방법을 생각하였습니다.

그러나 if문으로 문제에서 요구하는 숫자인지만 비교하면 메모리를 훨씬 효율적으로 사용할 수 있다고 판단하여 이 방법을 사용하였습니다.

 

---

 

• 소스코드 : 

N,D = map(int,input().split())
answer = 0
for i in range(1,N+1): # 1부터 N까지의 숫자를 탐색
    s_i = str(i) # 자릿수 연산을 위해 문자열로 변환
    l = len(s_i)
    for sliceCnt in range(l):  #몇 자릿수로 자르는지 range : 1 ~ len(i)
        for x in range(l-sliceCnt):  # 자르는 시작점
            s = s_i[x]
            for y in range(sliceCnt): # 자르는 자릿수
                s += s_i[x+y]
            if s == str(D):
                answer += 1
print(answer)