프로젝트 오일러 26번

count_temp=0
num_temp=0
for i in range(2,1001):
    count=0
    arr=[]
    left=i
    right=1
    for j in range(0,1000):      
        while(right<left):
            right=right*10
            if(right==0):
                break
        right=right%left
        arr.append(right)
        if(right==0):
            break
        right=right*10
    for k in range(1,len(arr)):
        if(arr[0]!=arr[k]):
            count=count+1
        else:
            if(count_temp<count):
                count_temp=count
                num_temp=i
            break
print(num_temp)
#반환 시간 : 0.4s

오랫동안 헤맨 2페이지의 세 번째 문제이다.

사실상 2페이지의 보스 문제 역이다.

순환마디가 가장 큰 수를 구하란다.

처음엔 단순히 단위분수를 /연산자로 나누어 뚫어져라 쳐다보았지만 해법이 보이지 않았다.

그러다가 노트에 나눗셈을 일일히 해 보았고, 

/연산자로 나누는 것보다 훨씬 더 많은 소수 부분의 자릿수를 얻을 수 있는 방법을 알아냈다.

소수 부분이 훨씬 더 길어졌으니 순환마디를 찾을 수 있겠구나 싶었지만

단순히 숫자만 많아져 어지러울 뿐 답을 찾을 수 없었다.

그러다가 생각난 것이,

'나머지'에 포커스를 맞추어 보자는 것이었다.

그동안 '몫'에만 포커스를 맞추었지만, 나머지에도 어떠한 규칙이 있는 것 같았다.

그렇게 노트에 나눗셈을 일일히 해보고 나머지를 눈여겨 보았더니

나머지가 같게 나올 때 순환마디가 시작하고 끝난다는 것을 알 수 있었다.

코드 부분을 보면

마지막 반복문 부분에서 순환마디의 마디수를 체크하게 되는데

나머지가 같아서 순환마디가 형성되는 경우와 나머지가 

같은 것이 나오지 않았는데 나누어 떨어져서 반복문이 끝나버리는 경우를 구분하기 위해

else 부분에 최종 판정을 내리도록 하였다.