[Project Euler] Problem 024

 

 

import java.util.ArrayList;
import java.util.List;
 
public class Problem024 {
    public final static int LIMIT = 1000000;
    
    public static void main(String[] args) {
        run();
    }
    
    public static void run() {
        int count = 0;
        List<Integer> list = new ArrayList<Integer>(); 
        
        for(int i = 0; i <= 9; ++i) {
            for(int j = 0; j <= 9; ++j) {
                if(!list.contains(j)) {
                    count += fac(9 - i);
                }
                
                if(count >= LIMIT) {
                    count -= fac(9 - i);
                    list.add(j);
                    break;
                }
            }
        }
        
        for(int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i));
        }
    }
    
    public static int fac(int num) {
        int result = 1;
        
        for(int i = 2; i <= num; ++i) {
            result *= i;
        }
        
        return result;
    }
}
 

 

정답: 2783915460

실행 시간: 500000ns

 

사실 손으로 푸는 게 더 쉬웠다. 그래서 일단 손으로 풀고 그 방식을 단계로 나눈 후 프로그래밍 언어로 옮겨썼다.

 

사전식 순서 이므로 첫 자리를 0부터 쓴다.

 

i) 첫 자리가 0일 때: count += 9!  //count: 362880

ii) 첫 자리가 1일 때: count += 9!  //count: 725760

iii) 첫 자리가 2일 때: count += 9!  //count: 1088640: 1000000 초과 -> 2~

 

count에서 9!을 뺀 후, 두 번째 자리부터 같은 과정을 다시 반복한다.

 

i) 두 번째 자리가 0일 때: count += 8!  //count: 766080

ii) 두 번째 자리가 1일 때: count += 8!  //count: 806400

iii) 두 번째 자리가 3일 때: count += 8!  //count: 846720

iv) 두 번째 자리가 4일 때: count += 8!  //count: 887040

v) 두 번째 자리가 5일 때: count += 8!  //count: 927360

vi) 두 번째 자리가 6일 때: count += 8!  //count: 967680

vi) 두 번째 자리가 7일 때: count += 8!  //count: 1008000: 1000000 초과 -> 27~

 

그리고 세 번째 자리, 네 번째 자리, … 쭉 반복한다.