백준 1019 책 페이지 - JAVA

1019 문제 링크

---

https://www.acmicpc.net/problem/1019

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
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));
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
        long[] counts = new long[10];
        long p = 1; // 자릿수
        while (p <= N) {
            long higher = N / (p * 10);
            long current = (N / p) % 10;
            long lower = N % p;
            for (int i = 0; i <= 9; i++) {
                counts[i] += higher * p;
                if (i < current) {
                    counts[i] += p;
                } else if (i == current) {
                    counts[i] += lower + 1;
                }
            }
            counts[0] -= p;
            p *= 10;
        }
        for (long count : counts) sb.append(count).append(" ");
        bw.write(sb.toString());
        bw.flush();
    }
}

 

알고리즘 설명

---

해당 문제에서 요구하는 조건을 찾기위해 브루트포스로 1부터 N까지 문자열이나 나머지 계산을 통해 자릿수를 하나씩 확인한다면 시간 초과를 걱정하지 않을 수 없습니다. N이 가질 수 있는 최대값이 10억이기 때문입니다.

 

하지만 숫자는 기본적으로 10진법 즉, 1부터 0까지 반복적으로 등장하기 때문에 이 반복 규칙을 활용해 자리별 등장 횟수를 구할 수 있습니다.

 

예를 들어, 19를 예시로 들어보겠습니다. 숫자를 자릿수 단위로 나누어 생각한다면 1의 자리는 9, 10의 자리는 1이 됩니다.

이후, 현재 자리 수를 나타내는 변수 p를 기준으로

1. higher : 현재 자리 수의 윗 자리 수가 얼마나 반복되었는지
2. current : 현재 자리 수에 해당하는 숫자
3. lower : 현재 자리 수의 아래 자리 숫자

세 변수의 값을 알고 있다면 0부터 9까지의 숫자가 몇 번 등장하는지 구할 수 있습니다.

먼저, p = 1을 시작으로 higher는 해당 자리 수가 몇 번 반복되는지를 구하는 것이기 때문에 19를 기준으로 10의 자리가 0인 경우, 10의 자리가 1인 경우까지 1의 자리수는 완전한 싸이클이 두 번 반복됩니다.

따라서, higher 만큼 각 숫자에 1씩 더해줍니다.

 

current와 lower는 함께 계산에 사용됩니다.

먼저, current는 현재 자리 숫자를 의미합니다. 예를 들어 19에서 p = 1인 경우에 current = 9이므로, 현재 자리 숫자가 0~8까지는 한 번씩 등장합니다. 즉, current보다 작은 숫자는 이전 완전한 사이클에서 이미 등장한 횟수를 의미하고, current 숫자는 지금 불완전 사이클에서 등장한 횟수를 의미합니다.

 

lower는 현재 자리보다 아래 자리 숫자가 몇 번 반복되는지를 나타냅니다. 예를 들어 19에서 10의 자리(p = 10)를 보면, lower = 9이므로 10의 자리 숫자 1은 1의 자리 0~9에서 각각 한 번씩 등장하게 됩니다. 즉, 불완전 사이클에서 현재 자리 숫자가 반복되는 횟수를 lower를 이용해 구할 수 있습니다. 1의 자리인 경우 lower는 존재하지 않고, 이후 10의 자리부터는 숫자의 사이클이 0부터 시작되므로, 불완전 사이클에서 현재 자리수는 해당 lower + 1 만큼 등장하므로 lower에 1을 더한 후, 해당 자리수의 해당하는 숫자 자리에 덧셈을 계산합니다.

 

마지막으로 자연수에서 맨 앞자리가 0인 경우의 숫자는 존재하지 않기 때문에, 해당 자릿수에서 0을 맨 앞으로 계산한 만큼 빼주어야 합니다.

 

dp도 그렇고, 구현도 그렇고 풀이과정이 복잡한 문제들은 풀이를 글로 적는게 참 힘든 것 같습니다.

 

코드 해석

---

1. p를 1부터 시작해서 1의 자리, 10의 자리, 100의 자리 순으로 올려가며 각 자릿수를 계산합니다.
2. 현재 자리수(p)를 기준으로 세 가지 값을 구합니다.
   
   • higher : 현재 자리 위의 숫자가 몇 번 반복되는지를 계산합니다.
   • current : 현재 자리 숫자를 구합니다.
   • lower : 현재 자리 아래의 숫자가 몇 번 반복되는지 구합니다.
3. 0부터 9까지의 숫자 등장 횟수를 배열 count에 저장합니다.
   
   • 먼저 higher를 이용해 완전한 사이클에서 각 숫자가 반복된 횟수를 더합니다.
   • 그 다음 current와 lower를 이용해 불완전 사이클에서 각 숫자가 몇 번 더 등장했는지를 계산합니다.
4. 맨 앞자리가 0인 경우는 자연수에 존재하지 않으므로, 0의 등장 횟수에서 불필요하게 더해진 만큼 빼줍니다.
5. p를 10배로 늘려 다음 자리수로 이동하고, N의 자릿수까지 반복합니다.
6. count배열에 저장된 숫자를 StringBuilder에 공백과 함께 더해주고 StringBuilder를 String형식으로 출력합니다.