2012/09/05 19:17

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

출처는 여기

문제

『코딩 인터뷰 완전 분석』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 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^
제가 보기엔 이 문제가 저번 문제보다는 훨씬 쉬워 보이네요 ㅎㅎ 출력이 단순하니 과정도 단순? ㅋㅋ

여러 숫자를 구할 수 있는 버전으로 작성했고, 정수 배열을 리턴하는 함수로 만들었습니다. 
배열의 첫번째 숫자가 0의 개수이고, 나머지는 0앞에 나오는 숫자들을 낮은 자리부터 차례로 붙여넣었습니다. 

내부적으로는 숫자 각각을 저장하는 원형 버퍼 배열을 생성해서 팩토리얼 계산을 수행했습니다. 
곱셈결과가 10이 넘으면 다음 자리수로 올리도록 되어 있고, 버퍼 사이즈보다 크면 버리도록 되어 있습니다.  
마지막 자리수가 0이면 버퍼의 시작 지점을 하나 올려서 10으로 나누기 한 효과를 내도록 했습니다. 

버퍼 사이즈를 얼마나 여유있게 해야 되느냐가 문제가 됩니다. 10의 두 약수 2와 5중 당연히 5가 덜 흔하므로,
5의 몇 제곱까지 곱해지느냐가 중요해서 log_5 n 으로 여유를 뒀습니다. 그 위쪽의 값들은 차츰 더 관심없는 
윗자리로 밀려나게 되므로 고려하지 않아도 됩니다.

결과:
n=2012 ::  [501, 8, 2, 9, 4, 4, 6, 9, 1, 0, 3, 2, 1, 1, 1, 8, 9, 1, 0, 4, 8]
n=10000 ::  [2499, 8, 0, 0, 9, 7, 5, 1, 0, 0, 8, 4, 9, 2, 0, 9, 3, 2, 8, 8, 7]
n=1000000 ::  [249998, 4, 4, 5, 2, 1, 4, 8, 5, 0, 5, 6, 7, 1, 6, 5, 2, 8, 5, 0, 1]

수정 9/6 ) 코드 좀 리팩토링해서 약간 짧고 간결하게 고쳤습니다. 


package insightbook.event.week2;

import java.util.Arrays;

public class FactorialDigits {

public static int[] factorialDigits(int n, int numberOfDigits) {

int count = 0;
int bufferSize = numberOfDigits + (int) (Math.log(n) / Math.log(5));
int[] buffer = new int[bufferSize];

int start = 0;
int currentNumberOfDigit = 1;
buffer[start] = 1;

for (int i = 2; i <= n; i++) {

int carry = 0;
for (int order = 0; order < currentNumberOfDigit; order++) {

int index = (start + order) % bufferSize;

buffer[index] *= i;
buffer[index] += carry;
carry = buffer[index] / 10;
buffer[index] %= 10;

}

while (carry > 0 && currentNumberOfDigit < bufferSize) {

buffer[(start + currentNumberOfDigit) % bufferSize] = carry % 10;
carry /= 10;
currentNumberOfDigit++;
}

while (buffer[start] == 0) {
start++;
start %= bufferSize;
currentNumberOfDigit--;
count++;
}
}

int length = Math.min(currentNumberOfDigit, numberOfDigits);
int[] result = new int[length + 1];
result[0] = count;
for (int i = 0; i < length; i++) {
result[i + 1] = buffer[(start + i) % bufferSize];
}

return result;
}

public static void main(String[] args) {

int[] ns = { 2012, 10000, 1000000 };

for (int n : ns) {
System.out.printf("n=%d :: %s\n", n,
Arrays.toString(factorialDigits(n, 20)));
}
}
}

덧글

  • kimchelsea 2012/09/06 03:04 # 답글

    나중에 자바도 한번 해봐야겠어요.!
    우선 C++부터 언능 다 해치우고 후우 ㅠㅠ
  • 성큼이 2012/09/06 13:39 #

    C++보다 자바가 좀 더 쉽습니다 ㅋㅋ C++의 간략화 버전이랑 비슷한 느낌이죠.
댓글 입력 영역