백준 1019. 책 페이지

문제 링크

난이도	정답률(_%)
Gold 1	36.369%

설계

• 마지막 책 페이지 N (최대 1,000,000,000)
• 어떻게 구현해야할지가 좀 막막했다. 규칙을 찾다가 말아서 그랬던 것 같다. 더 고민해보니 아래와 같은 규칙이 나왔다.
• 일의 자리일 경우 1개 증가, 10의 자리일 경우 10개 더 증가, 100의 자리일 경우 100개 더 증가, ...
• 따라서 각 자리수가 등장하는 횟수를 더 쉽게 계산하기 위해 해당 자리수의 시작과 끝을 한꺼번에 계산하도록 했다. 시작하는 페이지의 일의 자리는 0, 끝나는 페이지의 일의 자리는 9로 맞춘 다음 해당 자리수가 등장하는 횟수를 저장하도록 했다.

시간 복잡도

• 큰 로직: 마지막 페이지의 자릿수만큼 (최대 10번)
• 내부 로직
  • 끝 페이지의 일의 자리가 9가 될때까지 계산 (최대 10번, 내부 회전 최대 10번)
  • 시작 페이지의 일의 자리가 0이 될때까지 계산 (최대 9번, 내부 회전 최대 10번)
  • 해당 자리수의 횟수 저장 (10번)
• (100 + 90 + 10) * 10
• O(N)

공간 복잡도

• 각 숫자가 나오는 횟수를 저장할 int형 배열 (길이 10)

풀이

• 일의 자리부터 끝날 때 까지 아래 로직을 반복한다.
  • 끝 페이지의 일의 자리가 9가 될 때까지 각 숫자의 등장 횟수를 계산한다.
  • 이 때 끝 페이지의 값이 시작 페이지의 값보다 작아지면 멈춘다.
  • 시작 페이지의 일의 자리가 0이 될 때까지 각 숫자의 등장 횟수를 계산한다.
  • 페이지의 자리수를 감소시킨다.
  • 감소시킨 자리의 등장 횟수를 저장하고 등장 횟수를 *10 만큼 증가시킨다.

    등장 횟수를 저장할 때 마지막 페이지 - 시작 페이지 + 1를 곱한 이유는 그 자리수가 몇 줄(0~9가 한번 나올 때 마다 한 줄)인지 계산하기 위해서이다.

ex) 따라서 입력이 40페이지였다면 아래와 같이 계산된다.

• 39 페이지까지 각 자리 숫자 등장 횟수 저장(마지막 = 39 페이지)
• 10 페이지까지 각 자리 숫자 등장 횟수 저장(시작 = 10 페이지)
• 각 페이지의 자리수를 감소 (시작 = 1, 마지막 = 3)
• 감소시킨 자리수(일의 자리) 등장 횟수 저장.
• 다음으로 10의 자리를 계산하기 위해 등장 횟수 * 10
• 마지막이 9가 될 때까지 감소하며 계산하지만 그 전에 마지막 페이지가 시작 페이지보다 작아졌으므로 종료

결과

메모리	실행 시간
13052KB	76ms

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int lastPage = Integer.parseInt(br.readLine());
        int[] countNumber = new int[10];
        int startPage = 1;
        int point = 1;

        while (startPage <= lastPage) {
            while (lastPage % 10 != 9 && startPage <= lastPage) {
                calculate(lastPage, countNumber, point);
                lastPage--;
            }

            if (lastPage < startPage) {
                break;
            }

            while (startPage % 10 != 0 && startPage <= lastPage) {
                calculate(startPage, countNumber, point);
                startPage++;
            }

            lastPage /= 10;
            startPage /= 10;

            for (int i = 0; i < 10; i++) {
                countNumber[i] += (lastPage - startPage + 1) * point;
            }

            point *= 10;
        }

        for (int count : countNumber) {
            bw.write(Integer.toString(count) + " ");
        }

        bw.flush();
        bw.close();
    }

    public static void calculate(int page, int[] countNumber, int point) {
        while (page > 0) {
            countNumber[page % 10] += point;
            page /= 10;
        }
    }
}