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

계속 이어지는 인사이트 문제입니다. 





문제

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

자연수 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! = 93326215443944152681699238856266700490715968264381621468592963
    8952175999932299156089414639761565182862536979208272237582511852
    10916864000000000000000000000000
  3. 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.
  4.  정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.
  5. (심화 문제) 연속된 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));
}
}


전체 코드는 아래 주소에 올렸습니다.


덧글

  • 박성철 2012/09/08 13:19 # 답글

    와! 저도 0의 숫자만 구한다면 2와 5의 개수를 사용할 생각이었는데 마지막 숫자도 구할 수 있었군요. 생각이 짧았...
  • 정상혁 2012/09/08 16:26 #

    로그 쓰는게 코드는 더 간단하네요~ ^^;
  • 2012/09/09 19:29 # 삭제 답글

    소인수분해를 한다음에 2와 5의 쌍을 골라내고 나머지 숫자들을 한자리수만 계속 곱하게 하는게 간단하지않을까요?
  • 정상혁 2012/09/19 08:20 #

    전체 소인수 분해 대신 2와 5에 대해서만 소인수 분해하고, 나머지를 구하고자 하는 자릿수만 남겨서 곱했습니다..

    말씀하신 방법과 크게보면 같은 의도이고, 마지막 숫자를 한자리만이 아닌 여러자리를 구하는 심화문제를 만족시키려고 다소 화 시켰습니다.. 그런데 이것도 자리수가 어느정도 커지면 int가 넘쳐서 한계가 있기는하죠;
  • 전태준 2013/01/30 08:56 # 삭제 답글

    2에 대한 소인수 분해를 5에 대한 소인수 분해 횟수 만큼만 하면, 나중에 보정 작업이 없으니 더 좋지 않나요?
    아니면 이렇게 하는게 가독성이 떨어질까요?

    public class Test {

    public static final int MASK_NUMBER = 1000; //0의 앞자리 숫자, 10은 1자리, 100은 2자리

    public void calculate0(int n) {
    int count5 = 0; //n을 소인수 분해 시 5의 승 수
    int sumOfCount5 = 0; //count5의 합;
    int temp=1; //Factorial 계산에 유효한 수를 저장할 임시 변수

    while (n!=1) {
    temp = temp * n;


    for (; temp%5 ==0 ; temp/=5, count5++, sumOfCount5++);

    for (;temp%2 ==0 && count5 > 0; temp/=2, count5--);


    temp = temp % MASK_NUMBER;
    n--;

    }

    System.out.println (sumOfCount5+" "+temp);

    }
    }
댓글 입력 영역