책 페이지 (백준 1019번)

 

 

문제

지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다.

 

풀이

이 문제 역시 Z문제와 비슷하게 수학적으로 접근하였다.
우선 숫자가 abcd라고 할때, 역순으로 d c b a로 배열에 저장하였다. (각 숫자의 index가 자릿수랑 같게 해서 생각하기 편하게 할려고.)
그리고 각 자리수마다 숫자를 세어보았다.
근데 0일때는 또 달랐다. 왜냐하면 페이지가 784이면 784이지 0784가 아니기 때문이다.
0일때 우리가 1~9처럼 센 숫자를을 파악해보면 총 n자릿수의 숫자라고할 때
10^n + 10^(n-1) + . . . . + 10^1 + 10^0만큼 세어버리므로 그 만큼 최종적으로 빼주었다.

 

코드

import java.io.IOException;
import java.util.ArrayList;

public class Main {
	static int ans[] = new int[10];
	public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		int C = Integer.parseInt(br.readLine());
		ArrayList<Integer> page = new ArrayList<Integer>();
		while(true){
			page.add(C%10);
			if(C < 10) break;
			C = C/10;
		}
		int n = page.size()-1; //10의 몇승인지.
		for(int i =0; i< ans.length; i++){
			getPages(n,i,page);
			System.out.println(ans[i]);
		}
	}

	public static void getPages(int n, int num, ArrayList<Integer> page){
		if(n < 0) {
            //숫자가 0이면, 원래보다 10^n + 10^n-1 .... + 10^0 한거만큼 적으므로
			if(num == 0) {
				for(int i = page.size()-1; i >= 0; i--) {
					ans[num] = ans[num] - (int)Math.pow(10, i);
				}
			}
			return;
		}
		//숫자 : abcd ,,, page에는  dcba 
			//만약에 C차례면 10^a위치승-1 *a + 10^b위치승-1 *b 한거 기본으로 추가.
			for(int k =page.size()-1; k>n; k--){
				ans [num] = ans[num] + (int)Math.pow(10,k-1)*page.get(k);
			}		
			//a > i
			if(page.get(n) > num){
					// 10^a위치승만큼
					ans[num] = ans[num] + (int)Math.pow(10, n);
					}
				// a == i
			else if(page.get(n) == num){				
					//10^b위치승 *b + 10^c위치승 *c + 10^d위치승 *d +1
				for(int j = n-1; j >= 0; j--){
						ans[num] = ans[num] + (int)Math.pow(10,j)*page.get(j);
					}
					// 마지막 +1까지
					ans[num] = ans[num] + 1;
			}		
			//n-1일때도 소환
			getPages(n-1,num,page);
		return;
	}
}

 

복기

단순히 4321 124 등의 예시들을 통한 노가다로 규칙을 유추해내서 무식하게 풀었다.
주어진 숫자가 n이라고 할때, lgN만큼의 깊이로 재귀호출을 하고, 비교도 lgN, 계산도 lgN만큼 함으로 결국 시간복잡도가 $O(lgN)$ 인 것 같다.

 

결과

아이디	문제 번호	결과	메모리	시간	언어	코드 길이	제출 시간
howtolivelikehuman	1019	맞았습니다!!	12964KB	76ms	Java	1535B	2달 전