[Project Euler] Problem 005

 

이미 푼 문제다.(https://t0pli.tistory.com/49)

근데 풀고 1년 정도 지나서 다시 봤더니 뭔 말인지 하나도 모르겠어서 그냥 다시 풀었다.

 

 

import java.math.BigInteger;
import java.util.List;
import java.util.ArrayList;
 
public class Q005 {
    public static void main(String[] args) {
        System.out.println(run());
    }
    
    public static String run() {
        List<BigInteger> list = new ArrayList<BigInteger>(0);
        
        for(long i = 1L; i <= 20L; list.add(BigInteger.valueOf(i++)));
        
        return lcm(list.subList(1, list.size()), list.get(0)).toString();
    }
    
    public static BigInteger lcm(List<BigInteger> list, BigInteger b) {
        BigInteger val = (list.size() > 1) ? lcm(list.subList(1, list.size()), list.get(0))
                                           : list.get(0);
        
        return val.multiply(b).divide(val.gcd(b));
    }
}

 

기본적으로 다음에 의존해서 풀었다.

 

 

문제를 풀고 나면 사이트에서 볼 수 있는 내용이고, 출처는 위키백과라고 한다.

어떤 set의 최소공배수는 한 원소와 subset의 최소공배수로 보고, 

그 subset의 최소공배수는 다시 subset의 한 원소와 subset의 subset의 최소공배수로 보고, ...

를 반복하면 구할 수 있다는 내용이다.

 

여기서는 마지막 원소와 나머지로 나누는 방법을 예시로 보여줬는데, 두 집합으로 나누는 방법은 아무거나 상관없다.

맨 처음 원소와 나머지로 나누든 중간에 있는 원소와 나머지로 나누든 한 개의 원소와 나머지 원소들로 나누기만 하면 된다는 말이다. 나는 맨 처음 원소와 나머지 요소들로 나눴다.

 

 

1행 ~ 3행:

 BigInteger 는 두 정수 간의 GCD(Greate Common Divisor, 최대공약수) 값을 구하는  gcd  메소드도 가져다 쓰고 long 타입으로도 표현할 수 없을 만큼 큰 값이 나올까봐 import 했다(막상 해보니까 그렇게 큰 값은 나오지 않았다).

 List 와  ArrayList 는  subList  메소드 구현이 귀찮아서 import 했다.

구현하려면 할 수야 있겠지만... 문제를 푸는 의의는 여기에 있지 않기 때문에 굳이 손수 구현할 필요성을 못 느꼈다. 

11행 ~ 13행:

1~20의 리스트를 생성한다. 순서가 유지되는 집합이 머릿속에서 잘 그려져서  Set 이 아닌 

 List  인터페이스의 구현 클래스인  ArrayList  클래스를 사용해 문제를 풀었다. 

 HashSet  클래스와  subSet  메소드로 풀어도 상관없을 것 같다.

 

18 ~ 22행:

사실상 이 문제의 답.

다른 분들을 코드를 참고해서 풀고 싶었으나 이해가 안 돼서 (강제로) 혼자 풀었다. 역시 하면 된다.

 

한 원소와 나머지 원소들의 최소공배수를 구하기 위해 parameter는  List<BigInteger> 와

 BigInteger 로 선언했다.

이 과정을 한 원소와 한 원소만 남을 때까지 반복하는 것이므로 조건에 리스트의 크기가 1보다 크면 다시 자신을 호출하고 그렇지 않으면  list 의 요소(한 개 뿐이다)를  val 에 저장한다.

그리고 반환값은  val 과  b 의 곱을 둘의 최대공약수로 나눈 값, 즉  val 과  b 의 최소공배수가 된다.