okky에서 본 문제 factorial 100 without biginteger

biginteger없이 factorial 100! 을 기본자료형으로 출력

 

        int carry = 0;
        HashMap<Integer, Integer> q = new HashMap<Integer, Integer>();
        q.put(0, 1);
        for (int j = 1; j <= 100; j++) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int temp = q.get(i);
                temp = (temp * j) + carry;
                carry = temp / 10;
                q.put(i, (temp % 10));
                
            }
            while (carry != 0) {
            
                q.put(size, carry % 10);
                carry /= 10;
                size++;
            }
        }
 
        for (int i = q.size() - 1; i > -1; i--) {
            System.out.print(q.get(i));
        }

시간복잡도 O(n (log n)^2)

 

1. hashmap에 숫자를 연산한후 숫자 하나씩 집어넣음

2. 하위 for문의 연산이 끝난 후 carry에 값이 남아있으면 추가적으로 등록시킨다.

3. carry는 숫자 하나씩 집어넣기 위해 10으로 나눈 후 몫을 담고 있는 변수

4. 숫자가 역순으로 들어갔기 때문에 출력할땐 역순으로 뽑으면 된다.