백준 1019 책 페이지 Java

N쪽인 책의 페이지에 나온 0~9까지 숫자의 횟수를 출력하면 되는 문제이다.

내가 풀어내진 못했고,

알고리즘을 잘 하시는 마이구미님의 블로그를 통해 소스코드를 보고 이해하려고 노력한 문제이다.

시간이 좀 걸려서 이해했지만 까먹을 수 있으니 정리해야겠다.

 

11페이지를 입력받았을 경우엔

0	1	2	3	4	5	6	7	8	9
1	4	1	1	1	1	1	1	1	1

이렇게 출력이 되야한다.

1이 4번 나왔는데

1에서 한 번

10에서 한 번

11에서 두 번

총 네 번인 것이다.

 

암튼 이 문제의 경우엔 크기 10 배열을 선언하고

그 배열의 0번째 .. n번째 인덱스에 횟수를 넣어주어야 되는 것은 틀림없다.

누구나 그렇듯 처음엔 1부터 n까지 반복문을 돌며

charAt()으로든 %연산과 /연산으로든 출연 횟수를 구하려 했을 것이다.. 

나도 그랬지만 n의 최대값이 10억이니 될 리가 없다.

 

어떻게 풀어야 하냐면

시작값을 항상 끝자리를 0으로 만들고

n값의 끝자리를 9로 만들어서

반복되는 수를 일일이 더하지않고 한번에 더해주어야 한다.

이말이 참 어려웠다..

 

예를들어 입력받은 n값이 39이고

시작값을 10으로 만들었다고 가정하면

10 11 12 13 14 15 16 17 18 19

20 21 22 23 24 25 26 27 28 29

30 31 32 33 34 35 36 37 38 39

일의 자리의 0부터 9까지가 3번씩 반복되고

십의자리는 1부터 3까지 10회씩

이 규칙을 이용해서 반복문을 10번 돌려 각각 배열에 3회를 추가시키고

n을 나누기 10해서

n의 끝자리를 9로 만드는 과정에서 10회씩 추가한다.

 

 

이렇게라도  대충은 규칙을 이해해야 코드를 보기가 한결 수월할 것 같다.

코드를 보며 다시 정리해보자.

 

 
public class Q1019 {
 
    //파라미터로 받은 x를 10으로 나누며 자리수를 나눠 ans배열에 더한다.
    public static void cal(int x, int[] ans, int point) {
        while (x > 0) {
            ans[x % 10] += point; 
            x /= 10; 
        }
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] ans = new int[10];
        int point = 1; //자릿수
        int start = 1;
 
        while (start <= n) {
            // n의 끝자리 9로 만들기
            while (n % 10 != 9 && start <= n) {
                cal(n, ans, point); //감소시킨 n도 ans배열에 등장횟수를 증가시킨다.
                n--; //n을 감소시키면서
            }
 
            if (n < start) {
                break;
            }
 
            // start의 끝자리 0으로 만들기
            while (start % 10 != 0 && start <= n) {
                cal(start, ans, point);
                start++; //start를 증가시키면서 10으로 만든다.
            }
            start /= 10;
            n /= 10;
 
            for (int i = 0; i < 10; i++) { //반복되는 등장횟수를 더해준다.
                ans[i] += (n - start + 1) * point;
            }
            point *= 10; //다음 자리수로 넘어가기 위해 * 10을 해준다.
        }
 
        for (int i = 0; i < 10; i++) { //출력
            System.out.print(ans[i] + " ");
        }
 
    }
}

 

n으로 40를 받았다면

n = 40

start = 1

일 것이고.

 

 while (n % 10 != 9 && start <= n) {

          cal(n, ans, point); //감소시킨 n도 ans배열에 등장횟수를 증가시킨다.

          n--; //n을 감소시키면서

   }

여기 while문에서 n은 39가 될 것이다.

 public static void cal(int x, int[] ans, int point) {

        while (x > 0) {

            ans[x % 10] += point; 

            x /= 10; 

        }

    }

cal 메소드에서 x로 넘어온 40을 처리하면서 ans배열은

ans = [1, 0, 0, 0, 1, 0, 0, 0, 0, 0] 이 되고

 

지금 1인 start의 끝자리가 0이 되야 하기 때문에

1부터 9까지 다시 cal메소드의 파라미터로 넘기며

ans배열에 더해주고 start++로 10까지 증가 시킨다.

 

ans = [1, 1, 1, 1, 2, 1, 1, 1, 1, 1]

 

그다음

 start /= 10;

 n /= 10;

 

            for (int i = 0; i < 10; i++) { //반복되는 등장횟수를 더해준다.

                ans[i] += (n - start + 1) * point;

            }

 

start에 나누기 10을 해서 1이되고

n에 나누기 10을해서 3이 될것이다.

point 는 초기화한 그대로 1

n-start+1  -> 3 *point(1) -> 3

 

ans = [4, 4, 4, 4, 5, 4, 4, 4, 4, 4] 가 된다.

 

point *= 10; //다음 자리수로 넘어가기 위해 * 10을 해준다

 

point에 10을 곱해주면서

point = 10

n = 3

start = 1

이 된 상태로

끝자리를 다시 9로 만들기 위해 n을 감소시킬 것이다.

 // n의 끝자리 9로 만들기

            while (n % 10 != 9 && start <= n) {

                cal(n, ans, point); //감소시킨 n도 ans배열에 등장횟수를 증가시킨다.

                n--; //n을 감소시키면서

            }

public static void cal(int x, int[] ans, int point) {

        while (x > 0) {

            ans[x % 10] += point; 

            x /= 10; 

        }

    }

cal의 파라미터로 3이 들어가고 2가 들어가고 1이들어갈 것이고

ans[3] += 10

ans[2] += 10

ans[1] += 10

이들어가며 십의자리의 반복 등장한 수들도 ans배열에 더해질 것이다.

ans = [4, 14, 14, 14, 5, 4, 4, 4, 4, 4] 가 된다.

그리고 n이 0이 되면서

while (start <= n)

1인 start보다 n이 작아져서 가장 상위의 반복문을 나오게 된다.

 

9000을 n으로 입력받으면

n이 8999가 됐다가

899가 됐다가

89가됐다가

8이 된다.

 

이런식으로 수가 커도 몇번 반복하지 않는다.

이해하기도 어려운데

직접 생각해내서는 어떻게 푸는지 모르겠다. 대단들 하다.