[python]백준 1019번 : 책 페이지

문제

지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다.

나의 답

알고리즘

첫번째 코드

예시를 많이 얻기 위해 전체 경우의 수 구하는 가장 간단한 알고리즘 먼저 구현

n_list = list()
for z in range(0,1):
    n_list.append(int(input()))

for n in n_list:
    num_result = [0,0,0,0,0,0,0,0,0,0]
    for i in range(1,n+1):
        str_i = str(i)
        for tmp in str_i:
            num_result[int(tmp)]+=1
    print(num_result)1

숫자 하나씩 문자열로 받아서 각 자리수에 해당하는 배열값을 올리는 방식으로 진행

 

두번째 코드* => 나의 답

4328이라는 수를 예로 들어서 살펴보면,

처음에 first_in 함수에서는 주어진 수의 가장 큰 자릿수를 먼저 검사한다. 해당 예제에서는 4328이 1000의 자릿수를 가지고 있으므로 1000의 자리 먼저 검사한다. 1-3은 1000번 대, 2000번 대, 3000번 대의 수가 존재하므로 각각 1000번 씩의 경우의 수가 더해진다. 4000번 대 수는 뒤에 나온 수+1 만큼의 수만큼만 존재하므로 329만큼을 더해준다. 경우의 수가 하나 추가되는 이유는 4000이 있기 때문이다. (4000-4328까지는 329개의 수)

첫 함수를 지나면 현재 계산 중인 자릿수 loc_n을 1 줄여준다.

두번째로 들어가는 함수는 second_in이다. 이 함수는 자릿수가 1이 되기 전까지만 돌아간다. 해당 예제에서 100의 자릿수를 살펴보도록 하자. 100의 자리에서 1-9는 1000의 자리가 0일 때 1번 나타난다.

이는 econd_in 함수에 들어오는 모든 자릿수에서 같다. 해당 자릿수는 중간에 있는 자릿수이므로 바로 위의 자릿수가 0이면 해당 자릿수의 수가 0이 나올 수 없기 떄문이다.

ex_) 0011 은 3자리수가 아니라 2자리 수이다.

1번씩 나타나면서 100의 자릿수이므로 아래에 숫자가 100번 나올 수 있다. 따라서 100을 곱해준다.

0~9는 1000의 자리가 1이상일 때 나타나므로 (1000의 자리에 있는 수 - 1)번 꼭 나타난다. 4만 두고 본다면 해당 예제에서 1400번 대, 2400번 대, 3400번대가 나타날 수 있으니 3가지 경우가 있고, 각 경우마다 100의 자리수이므로 100을 곱해주어야한다.

ex_)1400-1499, 2400-2499, 3400-3499

이런 식으로 진행하다가 자릿수가 1이 되면 세번째로 last_in 함수에 들어가서 1의 자릿수를 검사한다. 1-9는 마찬가지로 1번 나오고 (10의 자릿수가 0일 때), 0~9는 1의 자리를 제외한 자리들의 수 (432) 에서 1을 뺀 만큼 나온다. 그리고 0-현재 1의 자리 수 까지는 1번 더 나온다.

import math

def loc_where(obj): # 자릿수 return
    i=0
    while obj:
        i+=1
        obj=obj[1:]
    return i

def first_in(n,arr):
    n_one = int(n[0])
    for i in range(1,n_one):
        arr[i]+=int(math.pow(10,len_n-1))
    arr[n_one]+=int(n[1:])+1
    return arr

def second_in(n,arr,loc):
    multi_num = int(math.pow(10,loc-1))
    for i in range(1,10):
        arr[i]+=multi_num
    for i in range(0,10):
        arr[i]+=(int(n[:len_n-loc])-1)*multi_num
    for i in range(0,int(n[len_n-loc])):
        arr[i]+=multi_num
    arr[int(n[len_n-loc])]+=(int(n[len_n-loc+1:])+1)
    return arr

def last_in(n,arr,loc):
    for i in range(1,10):
        arr[i]+=1
    for i in range(0,10):
        arr[i]+=(int(n[:len_n-1])-1)
    for i in range(0,int(n[len_n-1])+1):
        arr[i]+=1
    return arr

num = input()
loc_n = loc_where(num) # 현재 진행 중인 자릿수
len_n = len(num) # 주어진 수의 자릿수
num_array = [0,0,0,0,0,0,0,0,0,0]

if loc_n==1: # 한 자리 수일때
    for i in range(1,int(num)+1):
        num_array[i]+=1
else: # 두자리 수 이상일 때
    num_array = first_in(num,num_array)
    loc_n-=1
    while loc_n>1:
        num_array = second_in(num,num_array,loc_n)
        loc_n-=1
    num_array = last_in(num,num_array,loc_n)

for result in num_array:
    print(result, end=' ')

first_in, second_in, last_in 세 가지 함수로 나누었음

자릿수는 주어진 수의 자릿수(len_n)와 진행 중인 자릿수(loc_n)를 이용하여 구현

 

시간 복잡도

위의 모든 경우의 수를 계산하는 방법으로 진행했을 때는 6자리 수부터도 굉장히 느려졌다.

시간복잡도가 O(n*logn) 이다.

하지만 두번째 코드로 진행했을 때는 큰 수도 100ms을 넘지 않았다.

시간복잡도가 O(n) 이다.

이는 for문이 이중으로 겹쳐진 부분이 없어서 시간 복잡도가 훨씬 낮아진 것으로 보인다.

 

재귀함수

이 코드를 재귀함수로 바꾸면

 

세번째 코드 => 실험해본 알고리즘

def second_in(n,arr,loc):
    multi_num = int(math.pow(10,loc-1))
    for i in range(1,10):
        arr[i]+=multi_num
    for i in range(0,10):
        arr[i]+=(int(n[:len_n-loc])-1)*multi_num
    for i in range(0,int(n[len_n-loc])):
        arr[i]+=multi_num
    arr[int(n[len_n-loc])]+=(int(n[len_n-loc+1:])+1)
    loc-=1
    if loc<=1:
        return arr
    else:
        return second_in(n,arr,loc)



num = input()
loc_n = loc_where(num) # 현재 진행 중인 자릿수
len_n = len(num) # 주어진 수의 자릿수
num_array = [0,0,0,0,0,0,0,0,0,0]
if loc_n==1:
    for i in range(1,int(num)+1):
        num_array[i]+=1
else:
    num_array = first_in(num,num_array)
    loc_n-=1
    num_array = second_in(num,num_array,loc_n)
    num_array = last_in(num,num_array,loc_n)

for result in num_array:
    print(result, end=' ')

이렇게 아래에서의 반복문을 없애고 second_in만 재귀로 돌려주면 된다. 자릿수만큼 second_in 함수가 실행되므로 스택을 그렇게 많이 사용할 것 같진 않지만, 계속 배열을 매개변수로 넘기는 것이 좋을 것 같지는 않다.

 

메모리 사용

실제로 https://ideone.com/1qDKfb 라는 사이트에서 두번째 코드에 1000000000를 입력으로 준 결과 0.02s의 시간이 걸리고 9608KB의 메모리를 사용하였으나 세번째 코드를 사용한 결과 0.14s의 시간이 걸리고 23360KB의 메모리를 사용하였다.

 

느낀 점

쉬운 코드로 예시를 많이 만드는 방법도 시간이 적게 걸린다면 괜찮은 것 같다.