문제 풀이 날짜: 2023.10.13
포스트 작성일: 2023.10.16

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1019번: 책 페이지 (골드1)

 

키워드

수학, 나머지 연산(모듈러)

 

풀이 접근법

  • SWEA 5604번: [Professional] 구간 합 문제와 거의 유사한 문제이다. 구하는 배열은 같고 구간 합만 계산하지 않는다는 차이가 있다.
  • N이 10^9이하의 자연수이기 때문에 O(N)보다도 더 빠른 알고리즘이 필요하다.
  • N자리의 수가 있다고 할 때, 각 자리마다 떼어서 0~9가 몇 개 나왔는지를 살핀다.
  • 예를 들어 4자리 수의 0~9 출현 횟수를 구하고 싶다면, 일의 자리를 0~9로 변형시켜서 개수를 센다. 이 과정을 일의 자리부터 천의 자리까지 반복한다.
  • 7542라는 숫자가 있다고 할 때, 구간은 다음과 같이 나눈다.
  • 아래의 구간마다 0~9의 개수를 세면 된다.
7540 이상 7542 미만 사이의 모든 숫자
7500 이상 7540 미만 사이의 모든 숫자
7000 이상 7500 미만 사이의 모든 숫자
0000 이상 7000 미만 사이의 모든 숫자

 

  • 7500 이상 7540 미만 사이의 모든 숫자
    • 7500부터 7539까지 7과 5라는 숫자는 항상 반복적으로 나타난다. 따라서 7과 5의 개수는 7500부터 7539 사이의 모든 수의 개수이다. ⇒ 7539 - 7500 + 1 = 40개
    • 10의 자리에는 —0- 부터 —3-까지 0, 1, 2, 3이 출현한다. 이 수들은 각각 10회씩 출현한다. (총 40개)
    • 1의 자리에는 0부터 9가 모두 출현한다. 이 수들은 각각 4회씩 출현한다. (총 40개)
  • 7000 이상 7500 미만 사이의 모든 숫자
    • 7000부터 7499까지 7이라는 숫자는 항상 반복적으로 나타난다. 따라서 7의 개수는 7000부터 7499 사이의 모든 수의 개수이다 ⇒ 7499 - 7000 + 1 = 500개
    • 100의 자리에는 -0— 부터 -4— 까지 0, 1, 2, 3, 4가 출현한다. 이 수들은 각각 100회씩 출현한다. (예: 400부터 499까지 총 100회 출현한다.)
    • 10의 자리와 1의 자리에는 00부터 99가 온다. 100의 자리에 총 5가지 숫자가 오므로 이 수들은 각각 5회씩 출현한다. (예: 99의 경우 099, 199, 299, 399, 499의 5회)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static long start;
	private static long end;
	private static long mul;
	
	private static long[] numbers;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//1 <= N <= 1_000_000_000
		int N = Integer.parseInt(br.readLine());
		
		start = 1;
		end = N;
		mul = 1;
		
		numbers = new long[10];
        
		if(start == 0) start = 1; 
		while(start <= end) {
			while(start % 10 != 0 && start <= end) {
				calculatePlaces(start);
				start++; 
			}
			
			if(start > end) break;
            
			while(end % 10 != 9 && start <= end) {
				calculatePlaces(end);
				end--; 
			}
			
			long gap = (end / 10) - (start / 10) + 1;
			
			for(int i = 0; i < 10; i++) {
				numbers[i] += (gap * mul);
			}
            
			mul *= 10;
			start /= 10;
			end /= 10;
		}
		
		StringBuilder sb = new StringBuilder();
		for(long n : numbers) {
			sb.append(n).append(" ");
		}
		
		System.out.println(sb);
	}
	
	private static void calculatePlaces(long target) {
		for(long i = target; i > 0; i /= 10) {
			String s = Long.toString(i);
			int digit = s.charAt(s.length() - 1) - '0';
			
			numbers[digit] += mul;
		}
	}
}

수의 규칙성을 찾는 것이 꽤나 어려운 문제였다. 수의 각 자릿수와 나머지 연산을 적절히 활용하여 수가 출현한 개수를 세는 게 핵심이다. 처음에는 규칙을 찾는 것이 어려워 다른 블로그의 풀이를 참고하여 풀었다.

 

참고한 블로그

https://velog.io/@sinclairr/boj-1019

+ Recent posts