문제
1페이지부터 N페이지까지의 모든 페이지 번호에서, 0부터 9까지 각 숫자가 총 몇 번 등장하는지 구하라.
입력
N (1 ≤ N ≤ 1,000,000,000)이 주어진다.
출력
0부터 9까지 각 숫자의 등장 횟수를 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
11 | 1 4 1 1 1 1 1 1 1 1 |
풀이
시작(st)과 끝(ed)을 양쪽에서 좁혀가며 자릿수별로 각 숫자의 등장 횟수를 계산한다.
- st의 일의 자리가 0이 될 때까지 st를 증가시키며, 해당 수의 각 자릿수를 카운트한다
- ed의 일의 자리가 9가 될 때까지 ed를 감소시키며, 해당 수의 각 자릿수를 카운트한다
- 양 끝을 맞추었으면 st, ed를 10으로 나누고, 그 범위에서 각 숫자는 (ed-st+1) * digit번 등장한다
- digit을 10배로 늘리며 반복한다
핵심 아이디어: 일의 자리를 0~9로 맞춘 범위에서는 각 숫자가 균등하게 분포한다는 성질을 이용하여 자릿수를 한 단계씩 줄여가며 계산한다.
코드
package com.ssafy.an.day199;
import java.util.Scanner;
public class Day176BOJ1019t수 {
static int st, ed, digit;
static int[] cnt;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
digit = 1;
st = 1;
ed = sc.nextInt();
cnt = new int[10];
while (st <= ed) {
while (st % 10 != 0 && st <= ed) {
counting(st, digit);
st++;
}
while (ed % 10 != 9 && st <= ed) {
counting(ed, digit);
ed--;
}
if (st > ed)
break;
st /= 10;
ed /= 10;
for (int i = 0; i < 10; ++i) {
cnt[i] += (ed - st + 1) * digit;
}
digit *= 10;
}
for (long i : cnt) {
System.out.print(i + " ");
}
}
private static void counting(int num, int digit) {
while (num > 0) {
cnt[num % 10] += digit;
num /= 10;
}
}
}복잡도
- 시간: O((log N)²)
- 공간: O(1)