40. Champernowne's constant

1. 개요

  문제는 이곳에서 확인할 수 있다. 순환하지 않는 무한소수를 만드는 방법 중에 \(0.1234567891011\cdots\)과 같이 양의 정수를 무한히 붙여나가는 방법이 있다. \(d_n\)을 이 소수의 \(n\)번째 수라고 하자. 예를 들어 \(d_{12}=1\)이다. \(d_1 \times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000} \times d_{1000000}\)을 구하는 것이 문제의 목표이다.

2. 구현

  가장 간단한 방법은 \(i=1\)부터 적당히 큰 \(i\)까지 한번에 연결한 후 \(d_n\)을 찾는 것이다. 하지만 그 방법은 불필요한 자원의 낭비가 있으므로 \(i\)를 순차적으로 늘려가면서 \(d_n\)을 찾는 방법으로 구현한다.

# -*- coding: utf-8 -*-

i = 1
n_digit = 1
front_digit_count = 1

target_digit = [10**i for i in range(0,7)]
result = 1

while target_digit:

	if front_digit_count <= target_digit[0] <= front_digit_count + n_digit - 1:
		temp_target_digit = target_digit.pop(0)
		target_number = str(i)[temp_target_digit - front_digit_count]
		print(i)
		print('{n}: {number}'.format(n=temp_target_digit, number=target_number))
		result *= int(target_number)
		
	i += 1
	front_digit_count += n_digit
	if i % (10**n_digit) == 0:
		n_digit += 1
	
print('ANSWER: {answer}'.format(answer=result))

답은 210이다.

3. 생각해 볼 점

  데스크탑에서는 빠르게 답이 나왔다. 그리고 구현의 의도대로 컴퓨팅 파워가 낮은 환경에서도 잘 작동하는지 궁금하여 코드를 스마트폰에서 돌려보았다. 속도는 충분히 빨랐지만 틀린 답이 나왔다. 그 이유를 알아보니 실행한 파이썬의 버전이 달랐던 것이 문제였다. 즉, 스마트폰에서는 Python 2, 데스크탑에서는 Python 3를 사용하고 있다는 것이 차이의 원인이었다.

  Python 2와 Python 3 모두 반복문에서 사용되는 변수는 아래와 같이 외부의 영향을 받는다. 그런데 Python 2에서는 list comprehension에서도 마찬가지의 현상이 발생하고 Python 3에서는 그렇지 않다. 이를 반영하여 코드를 수정하니 두 환경에서 모두 같은 답이 나왔다.

i = 10
for i in range(0, 3):
    print(i)
print(i) # 2 for both python 2 and python 3

i = 10
print([i for i in range(0, 3)])
print(i) # 2 for python 2 but 10 for python 3