프로젝트 오일러 문제 - Problem 8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

이 문제를 풀기 위해서 가장 먼저 노가다 알고리즘(?)이 가장 먼저 생각난다.

처음 13자리 수의 곱을 구하고, 다음 13자리 수의 곱을 구하고, 계속 구해서 나온 결과들 987개의 곱들 중 비교해서 가장 큰 값을 찾아내면 되는 노가다 알고리즘이다.

하지만 출제자의 의도는 그리고 개발자로서 함양해야할 알고리즘은 노가다 알고리즘이 아닐 터.

우선 13자리의 숫자중 0이 하나라도 포함되어 있으면 13개 수의 곱(product)은 무조건 0이 되므로 제외시킬 수 있다.

생각해보니 1000번의 비교연산은 그렇게 많은 것이 아니다. 그래서 그냥 노가다로 풀었다. 물론, 0이 포함되면 제외시키는 String.contains("0") 이라는 메소드를 써서 처리할 수도 있는데 답이 금방 나오길래 말았다.

package archives;

public class ProjectEuler8 {
	static String number = "73167176531330624919225119674426574742355349194934"
							+"96983520312774506326239578318016984801869478851843"
							+"85861560789112949495459501737958331952853208805511"
							+"12540698747158523863050715693290963295227443043557"
							+"66896648950445244523161731856403098711121722383113"
							+"62229893423380308135336276614282806444486645238749"
							+"30358907296290491560440772390713810515859307960866"
							+"70172427121883998797908792274921901699720888093776"
							+"65727333001053367881220235421809751254540594752243"
							+"52584907711670556013604839586446706324415722155397"
							+"53697817977846174064955149290862569321978468622482"
							+"83972241375657056057490261407972968652414535100474"
							+"82166370484403199890008895243450658541227588666881"
							+"16427171479924442928230863465674813919123162824586"
							+"17866458359124566529476545682848912883142607690042"
							+"24219022671055626321111109370544217506941658960408"
							+"07198403850962455444362981230987879927244284909188"
							+"84580156166097919133875499200524063689912560717606"
							+"05886116467109405077541002256983155200055935729725"
							+"71636269561882670428252483600823257530420752963450";
	
	final static int THIRTEEN = 13;
	
	public static void main(String[] args) {
		Long maxProduct = 0L;
		Long temp = 1L;
		
		for(int i=0; i<number.length()-THIRTEEN+1; i++) {
			String numStr = number.substring(i, (i+THIRTEEN));
			temp = productResult(numStr);
			
			if(temp > maxProduct) {
				maxProduct = temp;
			}
		}
		
		System.out.println(maxProduct);
		
	}

	public static Long productResult(String digits)	{
		Long product = 1L;
		
		for (int i = 0; i < digits.length(); i++) {
			product *= Integer.parseInt(digits.substring(i,(i+1)));
		}
		
//		System.out.println(product);

		return product;
	}
}

처음엔 변수들을 int형으로 선언했었는데 답이 자꾸 2091059712 만 나오길래 로직이 잘못되었나 한참 생각해봐도 틀린 게 없는 것 같아서, 해외 포럼 몇몇개를 뒤져보니 C언어에서 같은 문제를 unsigned long long 형으로 바꿔주니 해결되었다는 걸 보고 나도 long 형으로 선언했더니 답이 나왔다.

이런 기본적인 실수는 나 스스로는 찾기 어려우니 처음부터 하지 않아야 할 것이다.