알고리즘 코딩 이벤트 2주차 문제와 1주차 1번 해설

https://gist.github.com/3634977 문제 풀이와 소스입니다.

좋아요좋아요

http://jaebaek.blogspot.kr/2012/09/210-173.html

좋아요좋아요

문제 풀이 입니다. .gist table { margin-bottom: 0; } 인사이트 알고리즘 코딩 이벤트 2주차 문제 풀이입니다. 문제 자연수 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! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다. 정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요. (심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^ 문제 풀이 풀이 #1 이 방법은 팩토리얼 계산을 하면서 뒤의 ‘0’ 숫자를 계속 카운트하고 필요 없는 숫자를 제거해 큰 숫자를 보관하지 않고 계산하도록 하는 방법입니다. 팩토리얼 결과를 다 담을 필요가 없으므로 각 수를 곱할 때마다 뒤의 0 숫자를 따로 기억(zeroTailSize 변수)하고 그 윗자리 숫자들도 0를 제외한 마지막 숫자에 영향을 미지는 자리까지의 수 만 기억(mask 변수 값으로 sum 값의 나머지만 보관)하도록 했습니다. 풀이 #2 이 방법은 최초에 시도했다가 포기했는데 정상혁님의 풀이에서 아이디어를 얻고 다시 시도했습니다. 뒤에 0이 생기는 이유는 소수 2와 5가 곱해져서 10이 생겼기 때문이므로 n!에서 2×5의 개수가 몇 개가 나오는 지 알면 됩니다. 이는 소수 2의 개수와 5의 개수를 구해서 2×5를 구성하는 개수, 즉, 2의 개수와 5의 개수 중 적은 수 만큼 10이 만들어지고 이 숫자 만큼 0이 뒤에 붙습니다. 그리고 소인수분해를 하면 당연히 2가 5보다 많이 나오므로 소수 5가 몇번 나오는지 만 알면 0의 개수를 알 수 있습니다. 제가 시도하다 실패한 이유는 0의 앞자리 수를 구하는 아이디어가 떠오르지 않았고 풀이#2가 (더 멋지긴 해도) 풀이#1 보다 효과적이라고 볼 수도 없기에 바로 #1로 넘어갔었습니다.(역시 새벽에 코딩하는 게 아니었…) 아무튼, 0 앞자리의 수는 n!에서 10을 구성하는 만큼의 소인수 2와 5를 제거한 나머지 수를 곱한 결과의 첫자리 수입니다. 이는 다시 말하면 소인수 2와 5를 제외한 너마지 수를 다 곱하고 이에 10을 구성하는 데 사용되지 않은 만큼의 2를 곱해서 구한 수의 첫자리 수라고 보면 됩니다. 그리고 곱하는 과정에서 우리가 관심있는 수는 첫자리 수이므로 그 수만 유지하도록 해서 곱해진 결과가 너무 커지지 않도록 유지하는 게 효과적입니다. 실행방법 풀이 #1

$ java org.fupfin.insight.event2a.SequentialFactorialZeroTailCounter 2012
n = 2012
Result [zeroTailSize=501, lastNoneZeroDigit=8]
$ java org.fupfin.insight.event2a.SequentialFactorialZeroTailCounter 10000
n = 10000
Result [zeroTailSize=2499, lastNoneZeroDigit=8]

풀이 #2

$ java org.fupfin.insight.event2a.PrimenumberFactorialZeroTailCounter 2012
n = 2012
Result [zeroTailSize=501, lastNoneZeroDigit=8]
$ java org.fupfin.insight.event2a.PrimenumberFactorialZeroTailCounter 10000
n = 10000
Result [zeroTailSize=2499, lastNoneZeroDigit=8]

view raw _README.md hosted with ❤ by GitHub This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters package org.fupfin.insight.event2a; public interface FactorialZeroTailCounter { /** * n!의 결과에서 뒷부분 0의 개수와 그 앞자리 수의 수를 반환한다. * @param n 팩토리얼을 계산하려는 수 * @return 끝자리 0의 개수와 그 앞자리 수 */ public Result count(int n); /** * 계산 결과를 저장할 데이터 구조체 */ public static class Result { /** 뒷자리 0의 개수 */ int zeroTailSize; /** 0 앞자리의 수 */ int lastNoneZeroDigit; public Result(int zeroTailSize, int lastNoneZeroDigit) { this.zeroTailSize = zeroTailSize; this.lastNoneZeroDigit = lastNoneZeroDigit; } @Override public boolean equals(Object obj) { if (this == obj || obj == null || getClass() != obj.getClass()) return false; Result other = (Result) obj; if (lastNoneZeroDigit != other.lastNoneZeroDigit || zeroTailSize != other.zeroTailSize) return false; return true; } @Override public String toString() { return "Result [zeroTailSize=" + zeroTailSize + ", lastNoneZeroDigit=" + lastNoneZeroDigit + "]"; } } } view raw FactorialZeroTailCounter.java hosted with ❤ by GitHub This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters package org.fupfin.insight.event2a; import static org.junit.Assert.assertEquals; import org.fupfin.insight.event2a.FactorialZeroTailCounter.Result; import org.junit.Test; public abstract class FactorialZeroTailCounterTest { public FactorialZeroTailCounterTest() { super(); } protected abstract FactorialZeroTailCounter getCounter(); @Test public void n이1일때는0은없고마지막숫자는1() { Result result = getCounter().count(1); assertEquals(new Result(0, 1), result); } @Test public void 알고_있는_값들을_검증() { int[] testNumbers = {20, 30, 40, 50, 100}; Result[] expectedResults = new Result[]{ new Result(4, 4), new Result(7, 8), new Result(9, 2), new Result(12, 2), new Result(24, 4) }; FactorialZeroTailCounter counter = getCounter(); for(int idx = 0; idx < testNumbers.length; idx ++) { Result result = counter.count(testNumbers[idx]); assertEquals(expectedResults[idx], result); } } } view raw FactorialZeroTailCounterTest.java hosted with ❤ by GitHub This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters package org.fupfin.insight.event2a; public class PrimenumberFactorialZeroTailCounter implements FactorialZeroTailCounter { @Override public Result count(int num) { int f = 1; int num2exp = 0; int num5exp = 0; IntRef n = new IntRef(); for (int i = 2; i <= num; i++) { n.value = i; num2exp += excludePrimeNumber(2, n); num5exp += excludePrimeNumber(5, n); f = (f * n.value) % 10; } int uncountednum2exp = num2exp – num5exp; while(uncountednum2exp — > 0) f = (f * 2) % 10; return new Result(num5exp, f); } private int excludePrimeNumber(int prime, IntRef num) { int count = 0; while (num.value % prime == 0) { num.value /= prime; count ++; } return count; } static class IntRef { int value; }; public static void main(String[] args) { if(args.length <= 0) { System.out.println("Usage: java org.fupfin.insight.event2a.PrimenumberFactorialZeroTailCounter number"); return; } FactorialZeroTailCounter counter = new PrimenumberFactorialZeroTailCounter(); Result result = counter.count(Integer.valueOf(args[0])); System.out.println("n = " + args[0]); System.out.println(result); } } view raw PrimenumberFactorialZeroTailCounter.java hosted with ❤ by GitHub This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters package org.fupfin.insight.event2a; public class PrimenumberFactorialZeroTailCounterTest extends FactorialZeroTailCounterTest { @Override protected FactorialZeroTailCounter getCounter() { return new PrimenumberFactorialZeroTailCounter(); } } view raw PrimenumberFactorialZeroTailCounterTest.java hosted with ❤ by GitHub This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters package org.fupfin.insight.event2a; import static java.lang.Math.*; public class SequentialFactorialZeroTailCounter implements FactorialZeroTailCounter { @Override public Result count(int n) { int mask = (int) pow(10, floor(log10(n)) + 1); int f = 1; int zeroTailSize = 0; for(int i = n; i > 1; i –) { f *= i; while(f % 10 == 0) { zeroTailSize ++; f /= 10; } f = f % mask; } return new Result(zeroTailSize, f % 10); } public static void main(String[] args) { if(args.length <= 0) { System.out.println("Usage: java org.fupfin.insight.event2a.SequentialFactorialZeroTailCounter number"); return; } SequentialFactorialZeroTailCounter counter = new SequentialFactorialZeroTailCounter(); Result result = counter.count(Integer.valueOf(args[0])); System.out.println("n = " + args[0]); System.out.println(result); } } view raw SequentialFactorialZeroTailCounter.java hosted with ❤ by GitHub This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters package org.fupfin.insight.event2a; public class SequentialFactorialZeroTailCounterTest extends FactorialZeroTailCounterTest { @Override protected FactorialZeroTailCounter getCounter() { return new SequentialFactorialZeroTailCounter(); } } view raw SequentialFactorialZeroTailCounterTest.java hosted with ❤ by GitHub 문제 풀이 기한이 있었네요. 풀어 놓고 안 올리고 있었는데… 좋아요좋아요

다른 일로 인사이트 책을 찾다가 이벤트를 발견하고
오밤중에 급히 풀어보게 되었네요~
(내일 휴가라는 것이 다행! 중요한 일이 있다는 것이 함정! )
http://artintel.tistory.com/entry/insightproblem

좋아요좋아요

http://jeremyko.blogspot.kr/2012/09/1.html

좋아요좋아요