[Project Euler] Problem 020

public class Problem020 {
    
    public static void main(String[] args) {
        long beginTime = System.nanoTime();
        
        System.out.println(run());
        
        long endTime = System.nanoTime();
        
        System.out.println("Running time: " + (endTime - beginTime) +"ns");
    }
    
    public static String run() {
        int[] arr = new int[158];
        int sum = 0;
 
        for(int i = 0; i < arr.length; ++i) {
            arr[i] = -1;
        }
        
        arr[arr.length - 1] = 1;
        
        for(int i = 1; i <= 100; ++i) {
            
            for(int j = (arr.length - 1); arr[j] >= 0; --j) {
                arr[j] *= i;
            }
            
            for(int j = (arr.length -1); (arr[j] >= 0) && (j >= 1); --j) {
 
                if((10 <= arr[j]) && (arr[j] <= 99)) {
                    if(arr[j - 1] < 0) {
                        arr[j - 1] = (arr[j] / 10);
                    } else {
                        arr[j - 1] += (arr[j] / 10);
                    }
                    
                    arr[j] %= 10;
                } else if((100 <= arr[j]) && (arr[j] <= 999)) { 
                    if((arr[j - 2] < 0) && (arr[j - 1] < 0)) {
                        arr[j - 2] = (arr[j] / 100);
                        arr[j - 1] = ((arr[j] % 100) / 10);
                        arr[j] %= 10;
                    } else if((arr[j - 2] < 0) && (arr[j - 1] >= 0)) {
                        arr[j - 2] = (arr[j] / 100);
                        arr[j - 1] += ((arr[j] % 100) / 10);
                        arr[j] %= 10;
                    } else if((arr[j - 2] >= 0) && (arr[j - 1] < 0)) {
                        arr[j - 2] += (arr[j] / 100);
                        arr[j - 1] = ((arr[j] % 100) / 10);
                        arr[j] %= 10;
                    } else if((arr[j - 2] >= 0) && (arr[j - 1] >= 0)) {
                        arr[j - 2] += (arr[j] / 100);
                        arr[j - 1] += ((arr[j] % 100) / 10);
                        arr[j] %= 10;
                    }
                }
            }
        }
        
        for(int i = 0; i < arr.length; ++i) {
            if(arr[i] >= 0) {
                sum += arr[i];
            }
        }
        
        return Integer.toString(sum);
    }
}
 

정답: 648

실행 시간: 7ms = 0.007초

16번 문제와 동일한 방식으로 풀었다. 

배열의 인덱스는 자리의 지수(10: 1, 100: 2, 1000: 3,  …)를, 요소의 값은 각 자리에 해당하는 자릿수를 나타낸다.

다만 이번에는 2가 아니라 바깥쪽 for 문의 변수인  i 를 통해 1부터 100을 곱할 뿐이다.

BigInteger 클래스를 사용하면 다음과 같다.

import java.math.BigInteger;
 
public class Example {
    
    public static void main(String[] args) {
        System.out.println(run());
    }
    
    public static String run() {
        BigInteger bi = BigInteger.ONE;
        int result = 0;
        
        for(int i = 1; i <= 100; i++) {
            bi = bi.multiply(new BigInteger(Integer.toString(i)));
        }
        
        while(!bi.equals(BigInteger.ZERO)) {
            result += bi.mod(BigInteger.TEN).intValue();
            bi = bi.divide(BigInteger.TEN);
        }
            
        return Integer.toString(result);
    }
}

실행 시간: 5ms