티스토리 뷰

간만에 포스팅인데, 인사이트에서 문제 풀기 이벤트 중이어서 참가해본다.

알고리즘 과목 하나 제대로 수강하지 않은 비전공자인 터라 얼마나 엉성하게 보일지는 모르겠지만, 답안이 포스팅인 안되고 있는 관계로 나도 한번 정리해 볼까 하고 몇자 남겨본다.

우선 문제는 다음과 같다.

자연수 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 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^


먼저 답부터 공개하자면,

input n: 2012
output : 8 501

input n: 10000
output : 8 2499


풀이 코드는 다음과 같다.

public class FactorialZerosAlgorithm {
	public static void main(String[] args) {
		FactorialZerosAlgorithm app = new FactorialZerosAlgorithm();
		app.solve(100);
	}
	
	public void solve(int n) {
		long[] result = factorial(n);
		System.out.printf("output : %d %d%n", result[0] % 10, result[1]);
	}

	private long[] factorial(int n) {
		long remain = 1;
		long zeros = 0;
		for (int i = 1; i <= n; i++) {
			remain *= i;
			int exp = (int) Math.log10(remain);
			if (exp > 0) {
				for (int j = 0; j < exp; j++) {
					if (remain % 10 == 0) {
						remain /= 10;
						zeros++;
					}
				}
				remain %= 100000;
			}
		}
		return new long[] {
				remain, zeros
		};
	}
}

알고리즘을 살펴보자면, 팩토리얼 계산을 수행하되, (성능상의 문제로 재귀호출보다는 반복문으로)
오른쪽 끝에서 부터 5자리만 저장하도록 변수(remain)를 작성하였다. 문제에서 n은 10000까지이므로 remain이라는 변수는 int 범위를 벗어나지 않기 때문에 int로 작성해도 상관없겠지만, 안전하게 long으로 잡아두었다.

오른쪽에서 0를 제외한 유효숫자 5개를 저장한 값에 차례대로 숫자를 곱하여 팩토리얼을 계산한다.
0의 갯수는 i를 곱하고 난 후, 몇 자리를 비교해야 할지 exp 변수로 저장하고, 10씩 나눠가면서 나누어 떨어지면 10를 나누고, 오른쪽 0의 갯수(변수 zeros)를 하나 추가한다. 다음 계산을 위하여 5자리만 제외하고 그 이상의 숫자는 다 지운다. (%= 100000)

이렇게 하여 끝자리 숫자는 오른쪽 끝 유효숫자 5개 중 제일 오른쪽 값이므로 %10으로 구하면 되고, 0의 갯수는 반복계산을 통해 구할 수 있다.


이상의 문제는 아래 인사이트에서 출간한 『코딩 인터뷰 완전 분석』라는 책을 통해 접할 수 있다.



코딩 인터뷰 완전 분석

저자
게일 라크만 맥도웰 지음
출판사
인사이트 | 2012-08-20 출간
카테고리
컴퓨터/IT
책소개
마이크로소프트, 그리고 애플, 구글에서 일한 경험이 있는 소프트...
가격비교


댓글
댓글쓰기 폼