[Project Euler] Problem 026

 

import java.util.List;
import java.util.ArrayList;
 
public class P026 {
    public static void main(String args[]) {
        System.out.print(run());
    }
    
    public static String run() {
        int remainder;
        int max = -1, ans = 2;
        
        
        for(int d = 2; d <= 1000; d++) {
            List<Integer> list = new ArrayList<Integer>(0);
            remainder = 1;
            
            int diff = 0;
            do {
                remainder = (remainder * 10) % d;
                list.add(remainder);
            } while((diff = list.lastIndexOf(remainder) - list.indexOf(remainder)) == 0);
            
            if(max < diff) {
                max = diff;
                ans = d;
            }
        }
        
        return Integer.toString(ans);
    }
}

 

10 ~ 11행:

변수 선언.  remainder 는 나눗셈 후 나머지가 저장될 변수다.  max 는 순환마디 길이를 비교하기 위한 변수고  ans 는  max 에 해당하는  d , 즉 정답이 저장될 변수다. 

 

14행:

2~1000의 정수  d 에 대해 반복 연산을 진행한다.

 

15 ~ 16행: 

초기값 설정

 

19 ~ 22행:

현재  d 에 대해 나머지 연산을 진행한 후 이 나머지를  list 에 추가한다.

그리고 이 과정을  list 에 같은 나머지 값이 2개 추가될 때까지(나머지가 중복될 때까지) 반복한다.

 lastIndexOf(E e) 는 리스트에서 주어진 요소가 여러 개일 때, 마지막 요소의 인덱스를,

 indexOf(E e) 는 리스트에서 주어진 요소가 여러 개일 때, 첫 번째 요소의 인덱스를 반환한다.

만약 주어진 요소가 하나 뿐이라면 두 메소드는 같은 값을 반환하게 되고,

그렇지 않다면 두 반환 값의 차이( diff )가 순환마디의 길이가 된다.

(엄밀히 말하면 순환마디의 길이는  diff + 1 이지만, +1을 하지 않아도 이전 순환마디의 길이와 비교하는 데에는 문제가 없다.

 3 < 5 나  3 + 1 < 5 + 1 이나 같다는 얘기다.)

 

24 ~ 27행:

이번에 구해진 순환마디의 길이( diff )가  max 보다 크다면  max 에  diff 를 대입한다.

그리고 이 때의  d  값을  ans 에 저장한다.

 d = 2 ~ d = 1000 까지의 반복을 마치면  max 에는 가장 긴 순환마디의 길이가,  ans 에는 그 때의  d  값이 저장되어 있다.

 

30행:

위와 같은 과정을 거쳐 구해진  ans  값을 문자열로 변환해 반환한다.

 

 

1/7을 생각해보자.

 

1.

 

2.

 

3.

...

 

1.

1을 7로 나누면 몫은 0, 나머지는 1이 된다.

 

2.

앞의 계산에서 나온 나머지에 10을 곱한다. 그리고 그 수에 대해 다시 나눗셈을 한다.

1을 7로 나눈 나머지에 10을 곱하고 그걸 다시 7로 나눈다.

이 때 몫은 1, 나머지는 3이 된다.

 

3.

앞에서 나온 나머지(3)에 다시 10을 곱하고, 그 수에 대해 나눗셈을 한다.

즉 30을 7로 나누어 몫과 나머지를 계산한다.

몫은 4, 나머지는 2가 된다.

 

 

이런 과정은 결국 다음과 같은 패턴의 반복이다.

 

1. 초기값은 1

2. 1을 7로 나눈다. 몫은 0, 나머지는 1.

3. 앞에서 나온 나머지 1에 10을 곱하고 그 수를 7로 나눈다. 몫은 1, 나머지는 3.

4. 앞에서 나온 나머지 3에 10을 곱하고 그 수를 7로 나눈다. 몫은 4, 나머지는 2.

5. 앞에서 나온 나머지 2에 10을 곱하고 그 수를 7로 나눈다. 몫은 2, 나머지는 6.

...

 

이를 일반화하면 다음과 같다.

1. 초기값은 1

2. 1을 d로 나눈다. 몫은 q1, 나머지는 r1

3. 앞에서 나온 나머지 r1에 10을 곱하고 그 수를 d로 나눈다. 몫은 q2, 나머지는 r2.

4. 앞에서 나온 나머지 r2에 10을 곱하고 그 수를 7로 나눈다. 몫은 q3, 나머지는 r3.

5. 앞에서 나온 나머지 r3에 10을 곱하고 그 수를 7로 나눈다. 몫은 q4, 나머지는 r4.

...

 

 

뭘 반복해야 할 지는 알았다. 이제 언제까지 반복해야 하는지만 알아내면 된다.

나에게 필요한 건 순환마디고, 순환마디는 소수점 아래의 숫자들로 이루어진다.

그리고 소수점 아래의 수는 위 과정에서 나오는 몫이다.

따라서 나눗셈을 진행하면서 이전에 나왔던 몫이 또 나오면 반복을 종료하면 된다.

 

...고 생각했으나 해보니 그렇지 않았다.

가령 1/998은 0.00100200400801603206412825651303...인데, 만약 몫의 중복으로 순환마디를 구분한다면 1/998의 순환마디는 00이 된다. 어떻게 순환마디를 구분할 수 있을까?

 

몫이 아닌 나머지의 중복으로 구분하면 된다. 즉 이전에 나왔던 나머지가 또 나오면 반복을 종료하는 것이다. 실질적으로 다음 몫에 영향을 미치는 것은 나머지기 때문이다.

 

1/7을 다시 보자.

1. 초기값은 1

2. 1을 7로 나눈다. 몫은 0, 나머지는 1.

3. 앞에서 나온 나머지 1에 10을 곱하고 그 수를 7로 나눈다. 몫은 1, 나머지는 3.

4. 앞에서 나온 나머지 3에 10을 곱하고 그 수를 7로 나눈다. 몫은 4, 나머지는 2.

5. 앞에서 나온 나머지 2에 10을 곱하고 그 수를 7로 나눈다. 몫은 2, 나머지는 6.

6. 앞에서 나온 나머지 6에 10을 곱하고 그 수를 7로 나눈다. 몫은 8, 나머지는 4.

7. 앞에서 나온 나머지 4에 10을 곱하고 그 수를 7로 나눈다. 몫은 5, 나머지는 5.

8. 앞에서 나온 나머지 5에 10을 곱하고 그 수를 7로 나눈다. 몫은 7, 나머지는 1

9. 1을 7로 나눈다. -> 과정 2와 같다! 

 

과정 9를 유심히 보자. 1을 7로 나누게 된다. 이는 맨 처음 했던 연산이므로 여기서 새로운 순환마디가 시작된다. 그럼 왜 처음에 했던 연산을 하게 된 것일까?

과정 8에서 나머지가 1이 나왔기 때문이다. 왜 과정 8에서는 나머지가 1이 된 걸까?

과정 7에서 나머지가 5가 나왔기 때문이다. 그리고 과정 7에서 나머지가 5가 된 이유는, ....

 

즉 나머지가 순환마디의 끝과 시작을 결정한다고 볼 수 있다.

과정 9는 과정 2에서 했던 것과 동일하다. 1을 7로 나누면 몫 1과 나머지 0을 얻게 되고, 이제 과정 3 ~ 과정 8을 반복하게 된다.

 

따라서 몫의 패턴, 즉 순환마디의 시작과 끝을 결정하는 것은 몫이 아닌 나머지다. 

그래서 코드 상에서 몫을 구하지도 않았고 22행의 반복문 탈출 조건은 나머지의 중복으로 한 것이다.