‘코딩 인터뷰 완전 분석 210쪽 17.3 변형 문제 풀이’

_README.md

인사이트 알고리즘 코딩 이벤트 2주차 문제 풀이입니다.

문제

자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

###실행 예

input n: 15
output: 3 8

###설명

15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

###조건

1. n의 범위는 1 이상, 10000 이하입니다.
2. 테스트 입력은 다음과 같습니다.
   20! = 2432902008176640000
   30! = 265252859812191058636308480000000
   40! = 815915283247897734345611269596115894272000000000
   50! = 30414093201713378043612608166064768844377641568960512000000000000
   100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
3. 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.
4. 정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.
5. (심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^

문제 풀이

풀이 #1

이 방법은 팩토리얼 계산을 하면서 뒤의 '0' 숫자를 계속 카운트하고 필요 없는 숫자를 제거해 큰 숫자를 보관하지 않고 계산하도록 하는 방법입니다.

팩토리얼 결과를 다 담을 필요가 없으므로 각 수를 곱할 때마다 뒤의 0 숫자를 따로 기억(zeroTailSize 변수)하고 그 윗자리 숫자들도 0를 제외한 마지막 숫자에 영향을 미지는 자리까지의 수 만 기억(mask 변수 값으로 sum 값의 나머지만 보관)하도록 했습니다.

풀이 #2

이 방법은 최초에 시도했다가 포기했는데 정상혁님의 풀이에서 아이디어를 얻고 다시 시도했습니다.

뒤에 0이 생기는 이유는 소수 2와 5가 곱해져서 10이 생겼기 때문이므로 n!에서 2x5의 개수가 몇 개가 나오는 지 알면 됩니다.

이는 소수 2의 개수와 5의 개수를 구해서 2x5를 구성하는 개수, 즉, 2의 개수와 5의 개수 중 적은 수 만큼 10이 만들어지고 이 숫자 만큼 0이 뒤에 붙습니다. 그리고 소인수분해를 하면 당연히 2가 5보다 많이 나오므로 소수 5가 몇번 나오는지 만 알면 0의 개수를 알 수 있습니다.

제가 시도하다 실패한 이유는 0의 앞자리 수를 구하는 아이디어가 떠오르지 않았고 풀이#2가 (더 멋지긴 해도) 풀이#1 보다 효과적이라고 볼 수도 없기에 바로 #1로 넘어갔었습니다.(역시 새벽에 코딩하는 게 아니었...)

아무튼, 0 앞자리의 수는 n!에서 10을 구성하는 만큼의 소인수 2와 5를 제거한 나머지 수를 곱한 결과의 첫자리 수입니다. 이는 다시 말하면 소인수 2와 5를 제외한 너마지 수를 다 곱하고 이에 10을 구성하는 데 사용되지 않은 만큼의 2를 곱해서 구한 수의 첫자리 수라고 보면 됩니다. 그리고 곱하는 과정에서 우리가 관심있는 수는 첫자리 수이므로 그 수만 유지하도록 해서 곱해진 결과가 너무 커지지 않도록 유지하는 게 효과적입니다.

실행방법

풀이 #1

$ java org.fupfin.insight.event2a.SequentialFactorialZeroTailCounter 2012
n = 2012
Result [zeroTailSize=501, lastNoneZeroDigit=8]
$ java org.fupfin.insight.event2a.SequentialFactorialZeroTailCounter 10000
n = 10000
Result [zeroTailSize=2499, lastNoneZeroDigit=8]

풀이 #2

$ java org.fupfin.insight.event2a.PrimenumberFactorialZeroTailCounter 2012
n = 2012
Result [zeroTailSize=501, lastNoneZeroDigit=8]
$ java org.fupfin.insight.event2a.PrimenumberFactorialZeroTailCounter 10000
n = 10000
Result [zeroTailSize=2499, lastNoneZeroDigit=8]

FactorialZeroTailCounter.java

package org.fupfin.insight.event2a;

public interface FactorialZeroTailCounter {

    /**
     * n!의 결과에서 뒷부분 0의 개수와 그 앞자리 수의 수를 반환한다.
     * @param n 팩토리얼을 계산하려는 수
     * @return 끝자리 0의 개수와 그 앞자리 수 
     */
    public Result count(int n);
    
    /**
     * 계산 결과를 저장할 데이터 구조체
     */
    public static class Result {
        /** 뒷자리 0의 개수 */
        int zeroTailSize;
        
        /** 0 앞자리의 수 */
        int lastNoneZeroDigit;
 
        public Result(int zeroTailSize, int lastNoneZeroDigit) {
            this.zeroTailSize = zeroTailSize;
            this.lastNoneZeroDigit = lastNoneZeroDigit;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj || obj == null || getClass() != obj.getClass()) 
                return false;
            
            Result other = (Result) obj;
            if (lastNoneZeroDigit != other.lastNoneZeroDigit || zeroTailSize != other.zeroTailSize)
                return false;
    
            return true;
        }

        @Override
        public String toString() {
            return "Result [zeroTailSize=" + zeroTailSize + 
                    ", lastNoneZeroDigit=" + lastNoneZeroDigit + "]";
        }
    }
}

FactorialZeroTailCounterTest.java

package org.fupfin.insight.event2a;

import static org.junit.Assert.assertEquals;

import org.fupfin.insight.event2a.FactorialZeroTailCounter.Result;
import org.junit.Test;

public abstract class FactorialZeroTailCounterTest {

    public FactorialZeroTailCounterTest() {
        super();
    }

    protected abstract FactorialZeroTailCounter getCounter();

    @Test
    public void n이1일때는0은없고마지막숫자는1() {
        Result result = getCounter().count(1);
        assertEquals(new Result(0, 1), result);
    }

    @Test
    public void 알고_있는_값들을_검증() {
        
        int[] testNumbers = {20, 30, 40, 50, 100};
        Result[] expectedResults = new Result[]{
                new Result(4, 4),
                new Result(7, 8),
                new Result(9, 2),
                new Result(12, 2),
                new Result(24, 4) };
        
        FactorialZeroTailCounter counter = getCounter();
        
        for(int idx = 0; idx < testNumbers.length; idx ++) {
            Result result = counter.count(testNumbers[idx]);
            assertEquals(expectedResults[idx], result);
        }
    }

}

PrimenumberFactorialZeroTailCounter.java

package org.fupfin.insight.event2a;

public class PrimenumberFactorialZeroTailCounter implements FactorialZeroTailCounter {

    @Override
    public Result count(int num) {
        
        int f = 1;
        int num2exp = 0;
        int num5exp = 0;
        
        IntRef n = new IntRef();
        
        for (int i = 2; i <= num; i++) {

            n.value = i;
            
            num2exp += excludePrimeNumber(2, n);
            num5exp += excludePrimeNumber(5, n);
            
            f = (f * n.value) % 10;
        }

        int uncountednum2exp = num2exp - num5exp;
        
        while(uncountednum2exp -- > 0)
            f = (f * 2) % 10;
        
        return new Result(num5exp, f); 
    }
    
    private int excludePrimeNumber(int prime, IntRef num) {

        int count = 0;
        while (num.value % prime == 0) {
            num.value /= prime;
            count ++;
        }

        return count;
    }
    
    static class IntRef {
        int value;
    };
    
    public static void main(String[] args) {
        
        if(args.length <= 0) {
            System.out.println("Usage: java org.fupfin.insight.event2a.PrimenumberFactorialZeroTailCounter number");
            return;
        }
        
        FactorialZeroTailCounter counter = new PrimenumberFactorialZeroTailCounter();
        Result result = counter.count(Integer.valueOf(args[0]));
        
        System.out.println("n = " + args[0]);
        System.out.println(result);
    }
}

PrimenumberFactorialZeroTailCounterTest.java

package org.fupfin.insight.event2a;

public class PrimenumberFactorialZeroTailCounterTest extends FactorialZeroTailCounterTest {

    @Override
    protected FactorialZeroTailCounter getCounter() {
        return new PrimenumberFactorialZeroTailCounter();
    }
}

SequentialFactorialZeroTailCounter.java

package org.fupfin.insight.event2a;

import static java.lang.Math.*;

public class SequentialFactorialZeroTailCounter implements FactorialZeroTailCounter {

    @Override
    public Result count(int n) {

        int mask = (int) pow(10, floor(log10(n)) + 1);
        
        int f = 1;
        int zeroTailSize = 0;
        
        for(int i = n; i > 1; i --) {
            
            f *= i;

            while(f % 10 == 0) {
                zeroTailSize ++;
                f /= 10;
            }

            f = f % mask;
        }
        
        return new Result(zeroTailSize, f % 10);
    }
    
    public static void main(String[] args) {
        
        if(args.length <= 0) {
            System.out.println("Usage: java org.fupfin.insight.event2a.SequentialFactorialZeroTailCounter number");
            return;
        }
        
        SequentialFactorialZeroTailCounter counter = new SequentialFactorialZeroTailCounter();
        Result result = counter.count(Integer.valueOf(args[0]));
        
        System.out.println("n = " + args[0]);
        System.out.println(result);
    }
}

SequentialFactorialZeroTailCounterTest.java

package org.fupfin.insight.event2a;

public class SequentialFactorialZeroTailCounterTest extends FactorialZeroTailCounterTest {

    @Override
    protected FactorialZeroTailCounter getCounter() {
        return new SequentialFactorialZeroTailCounter();
    }
}