[BOJ 1019] 책 페이지 (Java)

BOJ 1019 책 페이지

문제풀이

재귀를 통해 숫자를 붙혀나가는 방식을 시도해봤지만 그렇게 풀리는 문제가 아니였다. 그래서 풀이를 찾아보고 공부했다. 도저히 내가 생각해낼 수 있는 문제는 아니였다. 마이구미님의 해설과 백준님의 해설을 보고 공부하였다.

이 문제는 다음과 같은 규칙을 찾아야한다.

어떤 숫자 A의 일의 자리가 0이고 B의 일의 자리가 9일 때 A에서 B까지 0 ~ 9의 숫자가 등장하는 횟수는 (B/10 - A/10 + 1) * 원래 숫자에서의 자릿수다.

따라서 구현 순서는 다음과 같다.

1. 시작 페이지의 일의 자리가 0이 될 때 까지 ++, 마지막 페이지의 일의 자리가 9가 될 때 까지 -- 하며 그 과정에 등장하는 숫자들은 따로 세어준다.
2. 일의 자리가 0인 시작 페이지 ~ 일의 자리가 9인 마지막 페이지 사이에 0 ~ 9의 등장 횟수를 카운팅 배열에 더해준다.
3. 자릿수를 높여준다. (자릿수 * 10)
   • 계속 일의 자릿수를 이용하지만 실제로 원래 숫자에서 자릿수를 만들어주는 것이다.
4. 시작페이지가 마지막페이지 보다 커지는 순간까지 반복한다.

구현코드

import java.util.Scanner;

public class Main {
	
	static int[] cnt;
	static int start, end, digit;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		digit = 1;
		start = 1;
		end = sc.nextInt();
		
		cnt = new int[10];
		
		while(start <= end) {
			// 시작 페이지의 마지막 자리가 0이 될 때 까지 ++ 
			while(start % 10 != 0 && start <= end) {
				counting(start, digit);
				start++;
			}
			
			// 마지막 페이지의 마지막 자리가 9가 될 때 까지 -- 
			while(end % 10 != 9 && start <= end) {
				counting(end, digit);
				end--;
			}
			
			if(start > end) break;
			
			// 마지막 자릿수를 제거한다. 
			start /= 10;
			end /= 10;
			
			// start ~ end 사이의 0 ~ 9 갯수를 모두 센다.
			// 현재 자릿수 만큼 곱해줘야한다. 
			for(int i = 0 ; i < 10 ; ++i) {
				cnt[i] += (end - start + 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;
		}
	}
}