[백준] 1019 - 책 페이지

[문제링크]

1019번: 책 페이지

 

* 요약하자면 y번째 자리에 x번 수가 있을때

  - y자릿수를 만드는데 필요한 index를 x번 가산 ( 1 ~ y-1 자리에 등장하는 수 처리 )

  - 앞에서 등장한 prev 숫자들을 x*y번 가산 ( y+1 ~ 자리에 등장하는 수 처리 )

  - x보다 작은 수들을 y자릿수씩 가산 ( y 자리에 등장하는 수 처리 )

  - 3부분으로 나눠 처리하는 방법이다

 

0. 10단위로, 그 아랫 페이지까지 나오는 0~9의 갯수를 미리 계산해 저장한다

  - 1000페이지 미만까지 나오는 숫자는, 100페이지 미만에서 나오는 숫자들이 10회 반복해서 나오고

    + 1~9(앞자리)가 각 100번씩 나온다

  - 계산의 편의를 위해 0 또한 앞자리로 존재한다고 가정하고 연산, 마지막에 제거한다

 

1. 앞에서부터 숫자와 자릿수를 추출한다 ( cur, len )

 

2. len에 해당하는 index의 값을, cur번 더해준다 ( 

  - ex) 543에서 5를 처리할 때 : 5와 3(100의 자릿수)을 추출, index의 3번째(100까지 나오는 숫자) 배열을 5회 가산

 

3. prev배열은 앞에서 등장한 숫자 정보를 가지고 있으며, 현재 자리에서 반복하는 횟수만큼 가산된다

  - ex) 543에서 4를 처리할 때 : 5는 40회 가산되어야한다

 

4. 현재 cur에 대해, 0~cur-1까지의 숫자는 자릿수만큼 등장하므로, 가산해준다

  - ex) 543에서 4를 처리할 때, 0,1,2,3은 10번씩 등장할 것이다

 

5. 마지막 자리를 처리할때는, prev배열을 1회 추가로 가산해야 한다

  - 543에서 4를 처리할 때는 prev배열을 50X, 51X, 52X, 53X에 대해 4 * 10회 가산해주고,

  - 54X에 대한 처리는 X가 불확실하므로 아래 자릿수에서 하게 된다

  - 하지만 마지막 자릿수인 3에선 불확실한 수가 없으므로 540, 541, 542, 543 총 4 * 1회 해주게 된다

 

6. 맨 앞에 등장한 0을 제거한다.

  - 가장 앞의 0은 1의 자릿수에선 1번, 10의 자릿수에선 10번, 100의 자릿수에선 100번 등장한다.

  - ex) 543은 100의 자릿수이므로, 총 111번의 0이 등장한다

  - 주어진 수의 자릿수까지 1, 10, 100을 계속 빼준다

 

7. 나중에 다시 보기위해 작성한 설명인데, 미래의 내가 이걸 알아들을지 자신이 없다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		long[]page = new long[10];
		long[]prev = new long[10];
		long[]ans = new long[10];
		
		ArrayList<long[]>index=new ArrayList<>();
		index.add(page.clone());
		int cnt=1;
		//전처리
		for (int i = 0; i <= 9; i++) {
			for (int j = 0; j <= 9; j++) {
				page[j]*=10;
				page[j]+=cnt;
			}
			index.add(page.clone());
			cnt*=10;
		}

		String N = br.readLine();
		int len = N.length();
		
		//0번 자리부터
		for (int i = 0; i < N.length(); i++, len--) {
			int cur = N.charAt(i)-'0';

			long[] curIdx = index.get(len-1);
			long repeat = (long)Math.pow(10, len-1);
			for (int j = 0; j <= 9; j++) {
				ans[j]+=curIdx[j]*cur;
				ans[j]+=prev[j]*repeat*cur;//prev처리
			}
			
			//가장 앞자리 처리
			for (int j = 0; j < cur; j++) {
				ans[j]+=repeat;
			}
			
			prev[cur]++;
		}
		for (int j = 0; j <= 9; j++) ans[j]+=prev[j]; // prev배열 추가 1회 처리
		for (int i = 0; i < N.length(); i++) ans[0]-=Math.pow(10, i); // 맨 앞에 등장한 0 처리
		for (int i = 0; i <= 9; i++) System.out.print(ans[i]+" ");
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면