[백준]_1019번 : 책 페이지(파이썬 and C언어)

1019번: 책 페이지

골드 1치고 문제가 매우 단순해서 바로 덤벼들었던 문제이다. 하지만 나는 함정에 걸려든 것이었다.. 문제를 naive 하게 페이지 숫자를 문자열로 쪼개고(203 -> 2, 0, 3) 각 쪼개진 원소들의 개수만큼 정답 배열 안에 대입하면 되겠다는 접근을 한 것이다. 하지만 이런 브루트 포스식 접근 방법은 페이지 수가 10억까지 주어지는 문제에서는 시간 초과가 나오기 일쑤다. 그래도 일단 브루트 포스식으로 접근한 코드를 소개하겠다. 통과하지도 못한 코드를 왜 소개하냐고? 왜냐하면 나중에 개수를 직접 셀 때 내가 제대로 셌는지 알아보기 위해서이다.

실패 코드 1(파이썬)

import sys
input = sys.stdin.readline

arr = [0] * 10
user_input = int(input())
for num in range(1, user_input + 1):
    ls = list(str(num))
    for el in ls:
        arr[int(el)] += 1
print(" ".join(str(i) for i in arr))

실패 코드 2(C언어)

#include <stdio.h>

int main() {
    //정답 배열 arr
    int arr[10] = {0};
    int user_input;
    scanf("%d", &user_input);
    //페이지 수 카운트 1부터 user_input까지
    for (int num = 1; num < user_input + 1; num++) {
        //num은 상수로 존재해야 하기 때문에(반복문 때문) 변수 역할 tmp 사용
        int tmp = num;
        //자리 숫자를 arr에 각각 대입
        while (tmp) {
            arr[tmp % 10]++;
            tmp /= 10;
        }
    }
    //정답 출력
    for (int i = 0; i < 10; ++i)
        printf("%d ", arr[i]);

    return 0;
}

---

접근

문제를 어떻게 접근해야할지 고민하다가 결국 가장 큰 목표는 숫자를 입력받고 그 숫자 자체의 특성만으로 답을 끄집어 내야지 시간 초과가 나오지 않겠다는 생각이 들었다. 일단 숫자 자체가 답에 어떤 영향을 미치는지 알아보자. 일단 예시 숫자로 아무 숫자인 5828을 예시로 들어 보겠다. 

 

1부터 5828까지 0 ~ 9는 몇 번이나 등장할까? 10개의 숫자들을 몇 번이나 등장시키는지에 대해 가장 중요한 요소는 아마 자릿수가 아닐까 싶다. 왜냐하면 자릿수가 바뀔 때마다 고려해야 할 것이 많아지기 때문이다.

 

일단 아래와 같은 과정을 거쳐보자. 머릿속으로 10개의 숫자를 각각 세야되니까 머리가 많이 아플 것이다...

---

5828 

 

1000의 자리에서 세야 하는 숫자들 : 

[ 1000 ~ 4999 ]

1 ~ 4( 5-1 ) ( 1000번 )

 

[ 5000 ~ 5828 ] 

5 ( ( 828+1 )번 )

 

100의 자리에서 세야 하는 숫자들 : 

 

[ 100 ~ 999 ]

1 ~ 9 (100번)

 

[ 1000 ~ 4999 ]

0 ~ 9 ( ( 5-1 )x100번 )

 

[ 5000 ~ 5828 ]

0 ~ 7( 8-1 ) ( 100번 )

8 ( ( 28+1 )번 ) 

 

10의 자리에서 세야 하는 숫자들 : 

 

[ 10 ~ 99 ]

1 ~ 9 (10번)

 

[ 100 ~ 5799 ]

0 ~ 9 ( ( 58-1 )x10번 )

 

[ 5000 ~ 5828 ]

0 ~ 1( 2-1 ) ( 10번 )

2 ( ( 8+1 )번 ) 

 

1의 자리에서 세야 하는 숫자들 : 

 

[ 1 ~ 9 ]

1 ~ 9 (1번)

 

[ 10 ~ 5819 ]

0 ~ 9 (( 582-1 )번)

 

[ 5820 ~ 5828 ]

1 ~ 8 (1번)

 

<해석> 빨간 글씨로 표시된 숫자들은 전부 입력 숫자 5828에서 얻을 수 있는 규칙 요소들이며 초록색은 중간 자리들(100, 10)에서 개수와 관련된 규칙이다. 또한 잘 살펴보면 100의 자리와 10의 자리 사이의 규칙이 비슷하지 않은가? 따라서 아래와 같은 유추를 할 수 있다. 

"최고 자리 숫자(이 경우엔 천의 자리)와 일의 자리 숫자는 개별적인 계산이 필요하지만 그 중간은 규칙이 존재한다!!"

따라서 우리는 계산 장치를 3개(가장 높은 자리, 중간 자리, 일의 자리)만 만들면 성공인 것이다. 이제 함수를 한 개씩 만들어 보자.

시도 1(Python)

import sys
input = sys.stdin.readline

def opening(num, arr):
    target = int(num[0])
    for i in range(1, target):
        arr[i] += 10 ** (size - 1)
    arr[target] += int(num[1:]) + 1
    return arr

def middle(digit, arr, num):
    power_num = 10 ** (digit - 1)
    for i in range(1, 10):
        arr[i] += power_num
    for i in range(10):
        arr[i] += (int(num[:size - digit]) - 1) * power_num
    for i in range(0, int(num[size - digit])):
        arr[i] += power_num
    arr[int(num[size - digit])] += int(num[size - digit + 1:]) + 1
    return arr

def ending(num, arr):
    for i in range(1, 10):
        arr[i] += 1
    for i in range(10):
        arr[i] += int(num[:size - 1]) - 1
    for i in range(int(num[size - 1]) + 1):
        arr[i] += 1
    return arr

ans_ls = [0] * 10
page = input().strip()
# 상수
size = len(page)
# 변수
current_digit = len(page)
# 한 자리일 때
if current_digit == 1:
    for i in range(1, int(page) + 1):
        ans_ls[i] += 1
# 두 자리 이상일 때
else:
    ans_ls = opening(page, ans_ls)
    current_digit -= 1
    while current_digit > 1:
        ans_ls = middle(current_digit, ans_ls, page)
        current_digit -= 1
    ans_ls = ending(page, ans_ls)
# 출력
print(" ".join(str(i) for i in ans_ls))

 

시도 2(C언어)

#include <stdio.h>
#include <math.h>

int count_digit(int page_num) {
    int x = 0;
    while (page_num > 0) {
        page_num /= 10;
        x++;
    }
    return x;
}

void opening(int num, int *arr, int power) {
    int base_num = (int) round(pow(10, power - 1));
    int target = num / base_num;
    for (int i = 1; i < target; ++i) arr[i] += base_num;
    arr[target] += num % base_num + 1;
}

void middle(int num, int *arr, int digit) {
    int base_num = (int) round(pow(10, digit - 1));
    for (int i = 1; i < 10; ++i) arr[i] += base_num;
    for (int i = 0; i < 10; ++i) arr[i] += (num / (base_num * 10) - 1) * base_num;
    int target = (num / base_num) % 10;
    for (int i = 0; i < target; ++i) arr[i] += base_num;
    arr[target] += num % base_num + 1;
}

void ending(int num, int *arr) {
    for (int i = 1; i < 10; ++i) arr[i]++;
    for (int i = 0; i < 10; ++i) arr[i] += num / 10 - 1;
    for (int i = 0; i < num % 10 + 1; ++i) arr[i]++;
}

int main() {
    int ans_ls[10] = {0};
    int page;
    int size;
    int current_digit;

    scanf("%d", &page);
    size = count_digit(page);
    current_digit = size;

    if (current_digit == 1) for (int i = 1; i < page + 1; ++i) ans_ls[i]++;

    else {
        opening(page, ans_ls, size);
        current_digit--;
        while (current_digit > 1) {
            middle(page, ans_ls, current_digit);
            current_digit--;
        }
        ending(page, ans_ls);
    }
    for (int i = 0; i < 10; ++i) printf("%d ", ans_ls[i]);

    return 0;
}

여러모로 너무 힘들었지만 그만큼 뿌듯했던 문제였다...