[백준 1019] 책 페이지

백준 1019번: 책 페이지 - 상세 풀이

🔍 1. 문제 소개

백준 1019번 "책 페이지" 문제는 1부터 N까지의 페이지 번호에 각 숫자(0부터 9까지)가 몇 번씩 나타나는지 계산하는 문제입니다. 예를 들어, N이 11일 경우, 0은 1번, 1은 4번, 그 외 숫자는 각각 1번씩 나타납니다. N은 최대 1,000,000,000까지 가능합니다.

💡 2. 문제 해석

문제의 핵심은 1부터 N까지의 모든 페이지 번호를 순회하면서 각 자릿수의 숫자를 세는 것입니다. 단순히 반복문을 이용하여 모든 숫자를 검사하면 시간 초과가 발생할 수 있습니다. 따라서 효율적인 알고리즘을 사용하여 문제를 해결해야 합니다. 문제의 제약 조건은 N의 크기이며, 이는 알고리즘의 시간 복잡도에 큰 영향을 미칩니다.

🧠 3. 접근 방법

문제를 효율적으로 해결하기 위해서는 단순한 반복문 대신, 수학적인 접근을 활용합니다. 1부터 99까지의 숫자에서 각 자릿수 숫자의 개수를 파악하는 패턴을 찾고, 이 패턴을 이용하여 100부터 N까지의 숫자에 대한 계산을 최적화합니다. 각 자릿수의 숫자가 나타나는 빈도는 10의 배수마다 주기적으로 반복되는 특징을 가지고 있습니다. 이러한 특징을 이용하여 전체 숫자를 세지 않고도 빠르게 계산할 수 있습니다.

⚙️ 4. 구현 과정

1. 0부터 9까지의 숫자 개수를 저장할 `LongArray`를 선언합니다.

2. 10의 제곱수(1, 10, 100, 1000, ...)를 이용하여 범위를 나눕니다. 각 범위 내에서 각 자릿수의 개수를 계산합니다. 3. 각 범위에 대해, 각 자릿수가 몇 번 등장하는지 계산하고, LongArray에 누적합니다. 예를 들어, 100부터 199까지의 숫자에서 1은 100번(백의 자리) + 20번(십의 자리) + 10번(일의 자리) 나타납니다. 이를 일반화하여 계산식을 도출합니다. 4. 마지막으로 LongArray에 저장된 각 숫자의 개수를 출력합니다.

💻 5. 코드 설명

fun main() {
    val n = readLine()!!.toLong()
    val count = LongArray(10) { 0 }

    fun countDigits(num: Long, digit: Int): Long {
        var count = 0L
        var temp = num
        while (temp > 0) {
            if (temp % 10 == digit) count++
            temp /= 10
        }
        return count
    }


    for (i in 0..9) {
        var num = 0L
        var pow10 = 1L
        while(pow10 <= n) {
            val lowerBound = num
            val upperBound = minOf(n, num + 9 * pow10 -1)
            count[i] += (upperBound-lowerBound+1) / 10L * pow10
            if (i!=0) {
                count[i] += (upperBound - lowerBound + 1) % 10
            }
            
            num += pow10 * 10
            pow10 *= 10
        }
    }

    println(count.joinToString(" "))
}

코드 설명:

• `count` 배열은 각 숫자(0-9)의 개수를 저장합니다.

`pow10`은 10의 거듭제곱을 나타내며, 숫자 범위를 나누는 데 사용됩니다.

`lowerBound`와 `upperBound`는 현재 처리 중인 숫자 범위의 시작과 끝을 나타냅니다.

`(upperBound - lowerBound + 1) / 10`은 각 자릿수에 해당 숫자가 나타나는 횟수를 근사적으로 계산합니다.

⏱️ 6. 시간 복잡도와 공간 복잡도 분석

• **시간 복잡도:** `while` 루프는 최대 log₁₀(N)번 반복됩니다. 따라서 시간 복잡도는 O(log N)입니다. 이는 N이 아무리 커져도 반복 횟수가 지수적으로 증가하지 않음을 의미합니다.

**공간 복잡도:** `count` 배열은 크기가 10인 상수 크기이므로 공간 복잡도는 O(1)입니다.

🎯 7. 결론

이 문제는 단순한 반복문으로 해결하려고 하면 시간 초과가 발생하지만, 수학적인 패턴을 이용하여 효율적인 알고리즘을 설계하면 O(log N)의 시간 복잡도로 해결할 수 있습니다. 이를 통해 백만 단위 이상의 큰 N 값에도 효율적으로 문제를 해결할 수 있습니다. 추가적인 개선으로는 코드의 가독성을 높이고, 더욱 최적화된 수학적 공식을 도입하여 계산 속도를 더욱 높일 수 있을 것입니다. 이 문제를 통해 큰 숫자 처리 및 효율적인 알고리즘 설계의 중요성을 다시 한번 확인할 수 있었습니다.