재귀함수를 이용한 최소공배수 구하기

https://t0pli.tistory.com/147에서도 했지만

https://t0pli.tistory.com/171을 해보고 더 좋은 방법이 생각나 다시 풀었다.

 

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
 
public class Main {
    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();
        return lcm(list, list.size() - 1).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));
    }    
    
    public static BigInteger lcm(List<BigInteger> list, int n) {
        if(n == 1) {
            return list.get(0).multiply(list.get(1)).divide(list.get(0).gcd(list.get(1)));
        } else {
            BigInteger val = lcm(list, n - 1);
            return val.multiply(list.get(n)).divide(val.gcd(list.get(n)));
        }
    }
}

26행이 새로 만든 메소드다.

 

 

다음과 같이 실행시간을 재보면

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
 
public class Temp {
    public static void main(String[] args) {
        List<BigInteger> list = new ArrayList<BigInteger>(0);
        for(long i = 1L; i <= 20L; list.add(BigInteger.valueOf(i++)));
        
        long beginTime = System.nanoTime();
        lcm(list.subList(1, list.size()), list.get(0)).toString();
        long estimatedTime = System.nanoTime() - beginTime;
        System.out.println(estimatedTime);
        
        beginTime = System.nanoTime();
        lcm(list, list.size() - 1);
        estimatedTime = System.nanoTime() - beginTime;
        System.out.println(estimatedTime);
    }
 
    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));
    }    
    
    public static BigInteger lcm(List<BigInteger> list, int n) {
        if(n == 1) {
            return list.get(0).multiply(list.get(1)).divide(list.get(0).gcd(list.get(1)));
        } else {
            BigInteger val = lcm(list, n - 1);
            return val.multiply(list.get(n)).divide(val.gcd(list.get(n)));
        }
    }
}

후자가 훨씬 빠름을 알 수 있다.

$subList$ 메소드가 시간을 꽤 많이 잡아먹는 모양이다.