[BOJ 1019, Python 3] 책 페이지
https://www.acmicpc.net/problem/1019
1019번: 책 페이지
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.
www.acmicpc.net
풀이
|
1
2
3
4
5
6
7
|
n = int(input())
arr = [0] * 10
for i in range(1, n+1):
x = str(i)
for j in range(len(x)):
arr[int(x[j])] += 1
print(n, '-', arr)
|
cs |
이 코드는 O(N^2)로 답을 구하는 경우인데, 첫번째 자리수의 값을 제외한 나머지 값들을 9로 설정하고 확인해보면 규칙성이 나옵니다.
9 - [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
19 - [1, 12, 2, 2, 2, 2, 2, 2, 2, 2]
29 - [2, 13, 13, 3, 3, 3, 3, 3, 3, 3]
위처럼 10이 더해질 때마다 모든 값에 1이 증가하는 동시에 첫 번째 자릿수의 값이 10씩 증가합니다.
99 - [9, 20, 20, 20, 20, 20, 20, 20, 20, 20]
199 - [29, 140, 40, 40, 40, 40, 40, 40, 40, 40]
299 - [49, 160, 160, 60, 60, 60, 60, 60, 60, 60]
이렇게 100이 더해질 때마다 모든 값에 20이 증가하는 동시에 첫 번째 자릿수의 값이 100씩 증가합니다.
999 - [189, 300, 300, 300, 300, 300, 300, 300, 300, 300]
1999 - [489, 1600, 600, 600, 600, 600, 600, 600, 600, 600]
2999 - [789, 1900, 1900, 900, 900, 900, 900, 900, 900, 900]
1000이 더해질 때마다 모든 값에 300이 증가하는 동시에 첫 번째 자릿수의 값이 1000씩 증가합니다.
계속 이렇게 구해보면
첫 번째 자릿수: 10 ^ (숫자의 길이 - 1)만큼 증가
모든 값: (숫자의 길이 - 1) * 10 ^ (숫자의 길이 - 2)만큼 증가하게 됩니다.
=========================================================================
이제 첫 번째 자릿수를 제외한 모든 자릿수의 값을 9로 바꿨을 때의 규칙성을 알아보았습니다.
이것을 이용하여 답을 구할 때는 n을 입력 받으면 첫 번째 자릿수를 제외한 모든 자릿수의 값들을 9로 바꾸어주고, n이 나올 때까지 10000, 1000, 1, 10, ... 이렇게 10^k 꼴로 나오는 값들을 빼주면 됩니다.
예를들어서 1557의 값을 구한다고 가정해봅시다.
1999 - [489, 1600, 600, 600, 600, 600, 600, 600, 600, 600]
1999에서 1557이 되려면 일단 백의 자리수는 400을 빼야 합니다.
100을 뺀다면 위에서 확인한 대로 두 번째 자릿수 9의 값은 8로 변하면서 100이 줄어들고, 모든 값이 20이 줄어들 것 입니다.
1899 - [469, 1480, 580, 580, 580, 580, 580, 580, 580, 480]
그런데 답을 확인해보면 첫 번째 자릿수인 1의 값도 100이 줄어든 것을 확인할 수 있습니다.
왜 1의 값도 줄어들은 건지 생각해보면 1999에서 1899로 가는동안 첫 번째 자릿수인 1의 출현횟수도 동시에 줄어들기 때문인 것을 알 수 있습니다.
1799 - [449, 1360, 560, 560, 560, 560, 560, 560, 460, 460]
1699 - [429, 1240, 540, 540, 540, 540, 540, 440, 440, 440]
1599 - [409, 1120, 520, 520, 520, 520, 420, 420, 420, 420]
이렇게 해서 1599까지 구했습니다. 이제 1599를 1559로 변경해주면 됩니다.
1599 - [409, 1120, 520, 520, 520, 520, 420, 420, 420, 420]
1599에서 1589로 간다면 세 번째 자릿수인 9가 8로 변하면서 10이 줄어들고, 모든 값이 1이 줄어들 것 입니다.
거기다가 첫 번째 자릿수와 두 번째 자릿수도 출현횟수가 동시에 줄어들고 있으니 1의 출현횟수와 5의 출현횟수도 10이 줄어들을 것 입니다.
1589 - [408, 1109, 519, 519, 519, 509, 419, 419, 419, 409]
1579 - [407, 1098, 518, 518, 518, 498, 418, 418, 408, 408]
1579까지 구했으므로 마지막으로 1579를 1577로 변경해주면 됩니다.
1579 - [407, 1098, 518, 518, 518, 498, 418, 418, 408, 408]
1579에서 1578로 간다면 네 번째 자릿수인 9가 8로 변하면서 1이 줄어들고, 모든 값이 0으로 줄어들 것 입니다.
거기다가 첫 번째 자릿수, 두 번째 자릿수, 세 번째 자릿수도 출현횟수가 동시에 줄어들고 있으니 1의 출현횟수는 1이 줄어들고, 5의 출현횟수는 1이 줄어들고, 7의 출현횟수도 1이 줄어듭니다.
1578 - [407, 1097, 518, 518, 518, 497, 418, 417, 408, 407]
1577 - [407, 1096, 518, 518, 518, 496, 418, 416, 407, 407]
그래서 1577의 답은 [407, 1096, 518, 518, 518, 496, 418, 416, 407, 407]가 됩니다.
이런 방식으로 답을 구하면 됩니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
n = int(input())
val = [*str(n)[::-1]]
new_val = ['9' for _ in range(len(val)-1)] + [val[-1]]
arr = []
for i in range(10):
arr.append([10**i, i * int(10**(i-1))])
ans = [0] * 10
for i in range(len(new_val)):
for j in range(int(new_val[i])):
if i != 0:
ans[j+1] += (int(new_val[i-1])+1) * 10 ** (i-1)
for k in range(10):
ans[k] += max(1, i * 10 ** (i-1))
else: ans[j+1] += 1
for i in range(len(val)-2, -1, -1):
for j in range(9, int(val[i]), -1):
ans[j] -= arr[i][0]
for k in range(len(val)-1, i, -1):
ans[int(val[k])] -= arr[i][0]
for k in range(10):
ans[k] -= arr[i][1]
print(*ans)
|
cs |