<div id="readability-page-1" class="page"><div id="content">
       <div id="preamble">
<p>계속 이어지는 인사이트 문제입니다.</p>

<p><a href="http://www.insightbook.co.kr/wp-content/uploads/2012/08/%EC%BD%94%EB%94%A9%EC%9D%B8%ED%84%B0%EB%B7%B0-%ED%91%9C%EC%A7%801.jpg"><span><img src="http://www.insightbook.co.kr/wp-content/uploads/2012/08/%EC%BD%94%EB%94%A9%EC%9D%B8%ED%84%B0%EB%B7%B0-%ED%91%9C%EC%A7%801-204x300.jpg" alt="image" width="132" height="194" title="코딩인터뷰-표지"></span></a></p>
</div>
<div>
<h2 id="문제">문제</h2>
<div>
<p>코딩 인터뷰 완전 분석』210쪽 17.3 변형 문제</p>
<p>자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.</p>
<div>
<h3 id="실행_예">실행 예</h3>

</div>
<div>
<h3 id="설명">설명</h3>
<p>15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.</p>
<p>조건</p>
<div>
<ul>
<li>
<p>n의 범위는 1 이상, 10000 이하입니다.</p>
</li>
<li>
<p>테스트 입력은 다음과 같습니다.</p>
</li>
</ul>
</div>
<div>
<pre><code>20! = 2432902008176640000
30! = 265252859812191058636308480000000
40! = 815915283247897734345611269596115894272000000000
50! = 30414093201713378043612608166064768844377641568960512000000000000
100! = 93326215443944152681699238856266700490715968264381621468592963
8952175999932299156089414639761565182862536979208272237582511852
10916864000000000000000000000000</code></pre>
</div>
<div>
<ul>
<li>
<p>프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.</p>
</li>
<li>
<p>정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.</p>
</li>
<li>
<p>(심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^</p>
</li>
</ul>
</div>
</div>
</div>
</div>
<div>
<h2 id="풀이">풀이</h2>
<div>
<p>먼저 입력값이 2012와 10000일 때의 결과는 아래와 같습니다.</p>
<div>
<pre><code>input : 2012

output: 501 8


input : 10000

output: 2499 8</code></pre>
</div>
<p>제가 푼 방식은 10은 5와 2의 배수라는 점을 이용했습니다.
곱해지는 숫자를 2와 5로만 소인수 분해하고  그 갯수를 각각 누적해서 구합니다.
즉 최종 팩토리안 값의 약수 중에서 2와 5가 몇 번 들어가 있는지를 계산하는 것이죠.
그리고 2,5가 아닌 나머지 약수는 구하고자하는 자릿수만큼만 잘라서 보관합니다.</p>
<p>예를 들면 5!에서 0의 갯수가 0이 아닌 마지막 숫자를 구한다면</p>
<div>
<pre><code>5! = 1 * 2 * 3 * 4 *5 = 2^3 * 5 * 3</code></pre>
</div>
<p>이이므로 2는 3번, 5는 1번 들어갑니다. 0의 갯수는 2,5가 짝이 맞는 갯수이므로 둘 중에 작은 숫자인 5의 약수의 갯수, 즉 1개입니다.</p>
<p>그리고 마지막 0이 아닌 숫자는 나머지 약수의 마지막 숫자인 3과 5와 짝이 맺어지지 못한 2의 배수를 곱해서 구합니다.</p>
<p>여기서는 약수인 2중 1개는 5와 짝이 맺어졌고, 나머지 2개가 남았으므로 2^2*3 = 12, 마지막 숫자만 남기면 2입니다.</p>
<p>테스트 코드에서는 이미 알려진 숫자를 검증했습니다.</p>
<div>
<pre><code data-lang="java">public class FactorianAnalyzerTest {
    FactorianAnalyzer analyzer = new FactorianAnalyzer();

    @Test

    public void test5(){
        assertFactorianResult(5, 1, 2);
    }

    @Test
    public void test15(){
        assertFactorianResult(15, 3, 8);
    }

    @Test
    public void test20(){
        assertFactorianResult(20, 4, 4);
    }

    @Test
    public void test30(){
        assertFactorianResult(30, 7, 8);
    }

    @Test
    public void test40(){
        assertFactorianResult(40, 9, 2);
    }

    @Test
    public void test50(){
        assertFactorianResult(50, 12, 2);
    }

    @Test
    public void test100(){
        assertFactorianResult(100, 24, 4);
    }</code></pre>
</div>
<p>그리고 꼭 마지막 1개의 숫자가 아닌 여러 숫자로 구할 수 있도록 확장했기 때문에 그것도 검증해보았습니다.</p>
<div>
<pre><code data-lang="java">public class FactorianAnalyzerNonZeroTwoDigitsTest {

    FactorianAnalyzer analyzer = new FactorianAnalyzer();

    @Test
    public void test5(){
        assertFactorianResult(5, 2, 1, 12);
    }

    @Test
    public void test6(){
        assertFactorianResult(6, 2, 1, 72);
    }

    @Test
    public void test7(){
        assertFactorianResult(7, 3, 1, 504);
    }

    @Test
    public void test8(){
        assertFactorianResult(8, 2, 1, 32);
    }

    private void assertFactorianResult(int n,  int numOfLastNonZeroDigits, int expectedZeroCount, int expectedNonzeroDigit) {
        FactorianResult result = analyzer.countZero(n, numOfLastNonZeroDigits);
        assertThat(result.getZeroCount(), is(expectedZeroCount));
        assertThat(result.getNonZeroDigits(), is(expectedNonzeroDigit));
    }
}</code></pre>
</div>
<p>전체 코드는 아래 주소에 올렸습니다.</p>
<div>
<ul>
<li>
<p><a href="https://github.com/benelog/quiz/blob/master/src/test/java/net/benelog/quiz/insight/FactorianAnalyzerTest.java">FactorianAnalyzerTest.java</a></p>
</li>
<li>
<p><a href="https://github.com/benelog/quiz/blob/master/src/main/java/net/benelog/quiz/insight/FactorianResult.java">FactorianResult.java</a></p>
</li>
<li>
<p><a href="https://github.com/benelog/quiz/blob/master/src/main/java/net/benelog/quiz/insight/FactorianAnalyzer.java">FactorianAnalyzer.java</a></p>
</li>
<li>
<p><a href="https://github.com/benelog/quiz/blob/master/src/test/java/net/benelog/quiz/insight/FactorianAnalyzerNonZeroTwoDigitsTest.java">FactorianAnalyzerNonZeroTwoDigitsTest.java</a></p>
</li>
</ul>
</div>
</div>
</div>
    </div></div>

JBake

계속 이어지는 인사이트 문제입니다.
http://www.insightbook.co.kr/post/3876
문제
코딩 인터뷰 완전 분석』210쪽 17.3 변형 문제
자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.
실행 예
input n: 15
output: 3 8
설명
15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.
조건
n의 범위는 1 이상, 10000 이하입니다.
테스트 입력은 다음과 같습니다.
20! = 2432902008176640000
30! = 265252859812191058636308480000000
40! = 815915283247897734345611269596115894272000000000
50! = 30414093201713378043612608166064768844377641568960512000000000000
100! = 93326215443944152681699238856266700490715968264381621468592963
8952175999932299156089414639761565182862536979208272237582511852
10916864000000000000000000000000
프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.
정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.
(심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^
풀이
먼저 입력값이 2012와 10000일 때의 결과는 아래와 같습니다.
input : 2012
output: 501 8
input : 10000
output: 2499 8
제가 푼 방식은 10은 5와 2의 배수라는 점을 이용했습니다.
곱해지는 숫자를 2와 5로만 소인수 분해하고  그 갯수를 각각 누적해서 구합니다.
즉 최종 팩토리안 값의 약수 중에서 2와 5가 몇 번 들어가 있는지를 계산하는 것이죠.
그리고 2,5가 아닌 나머지 약수는 구하고자하는 자릿수만큼만 잘라서 보관합니다.
예를 들면 5!에서 0의 갯수가 0이 아닌 마지막 숫자를 구한다면
5! = 1 * 2 * 3 * 4 *5 = 2^3 * 5 * 3
이이므로 2는 3번, 5는 1번 들어갑니다. 0의 갯수는 2,5가 짝이 맞는 갯수이므로 둘 중에 작은 숫자인 5의 약수의 갯수, 즉 1개입니다.
그리고 마지막 0이 아닌 숫자는 나머지 약수의 마지막 숫자인 3과 5와 짝이 맺어지지 못한 2의 배수를 곱해서 구합니다.
여기서는 약수인 2중 1개는 5와 짝이 맺어졌고, 나머지 2개가 남았으므로 2^2*3 = 12, 마지막 숫자만 남기면 2입니다.
테스트 코드에서는 이미 알려진 숫자를 검증했습니다.
public class FactorianAnalyzerTest {
    FactorianAnalyzer analyzer = new FactorianAnalyzer();
    @Test
    public void test5(){
        assertFactorianResult(5, 1, 2);
    }
    @Test
    public void test15(){
        assertFactorianResult(15, 3, 8);
    }
    @Test
    public void test20(){
        assertFactorianResult(20, 4, 4);
    }
    @Test
    public void test30(){
        assertFactorianResult(30, 7, 8);
    }
    @Test
    public void test40(){
        assertFactorianResult(40, 9, 2);
    }
    @Test
    public void test50(){
        assertFactorianResult(50, 12, 2);
    }
    @Test
    public void test100(){
        assertFactorianResult(100, 24, 4);
    }
그리고 꼭 마지막 1개의 숫자가 아닌 여러 숫자로 구할 수 있도록 확장했기 때문에 그것도 검증해보았습니다.
public class FactorianAnalyzerNonZeroTwoDigitsTest {
    FactorianAnalyzer analyzer = new FactorianAnalyzer();
    @Test
    public void test5(){
        assertFactorianResult(5, 2, 1, 12);
    }
    @Test
    public void test6(){
        assertFactorianResult(6, 2, 1, 72);
    }
    @Test
    public void test7(){
        assertFactorianResult(7, 3, 1, 504);
    }
    @Test
    public void test8(){
        assertFactorianResult(8, 2, 1, 32);
    }
    private void assertFactorianResult(int n,  int numOfLastNonZeroDigits, int expectedZeroCount, int expectedNonzeroDigit) {
        FactorianResult result = analyzer.countZero(n, numOfLastNonZeroDigits);
        assertThat(result.getZeroCount(), is(expectedZeroCount));
        assertThat(result.getNonZeroDigits(), is(expectedNonzeroDigit));
    }
}
전체 코드는 아래 주소에 올렸습니다.
FactorianAnalyzerTest.java
FactorianResult.java
FactorianAnalyzer.java
FactorianAnalyzerNonZeroTwoDigitsTest.java

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

댓글