문제

『코딩 인터뷰 완전 분석』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 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^

문제의 예시인 15!만 구해도 자리수가 상당히 커진다.

문제의 의도는 마지막에 0이 몇개나오는지, 그리고 그 앞자리가 무엇인지 이므로 앞의 길다란 자리수는 버려서, 숫자가 무한정 커지지 않도록한다(속도도 좀 빨라진다).

1. 끝자리가 0으로 끝날때마다 0의 카운트를 하나 늘리고 원  숫자를 줄인다.

2. 나머지 숫자를 입력값 이상의 자리수가 나오지 않도록 줄인다.

(처음에 아무 생각없이 한자리만 저장했었는데, 25*4같이 끝자리에 0이 2개이상 오는경우 망가질 수 있음을 발견하고 처음 입력하는 수의 자리수만큼을 남기도록 수정했다. 더불어, 문제의 5번 조건인 연속된 0앞의 여러숫자를 구하는것도 그닥 어렵잖게 될 듯?)

문제의 예제는 10000만 까지만 다루고 있어서 숫자가 무한정 커지지는 않는데..

그 이상으로 큰 숫자가 들어가면 문제가 생긴다. 추가로 생각해볼만한 부분.

그럼 이만, 코드.

결과는

(15, 3, 8)
(20, 4, 4)
(30, 7, 8)
(40, 9, 2)
(50, 12, 2)
(100, 24, 4)
(2012, 501, 8)
(10000, 2499, 8)