Project Euler Problem4

몇 주전에 풀다가 답이 틀려 잠깐 멈췄던 부분이 있었는데..

1시간 가량 찾지 못했던 해답을 오늘 3분만에 풀었다.

알고리즘 문제를 하루에 하나 풀어보자고 하는데.. 역시 뭐 생각만큼 쉽지는 않다.

Problem4. A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

직접 푼 알고리즘)

C++환경에서 for문 2개를 써서 풀었다.

999*999부터 100*100까지 비교했다.

여기서 palindrome인지 확인하는 부분이 핵심.

필자는 각 자리의 수를 구하여 최대 6칸의 배열(nArray[6])을 만들었다.

(각 자리의 수를 구하는데 쓸데 없이 코드가 길어졌다...)

최대 자리가 0일때는 5자리 수기 때문에

가운데 자리를 제외한 일의 자리와 만의 자리, 십의자리와 천의자리를 비교.

최대 자리가 0이 아니라면 일의 자리 - 십만의 자리, 십의 자리와 만의 자리, 백의 자리와 천의 자리를 비교한다.

수도 코드는 대충

for(100~999)

for(100~999)

Num1*Num2

if(N[0] == 0)

compare N[1] N[5]

compare N[2] N[4]

else

compare N[0] N[5]

compare N[1] N[4]

compare N[2] N[3]

if(max?)

}

}

뭐 대부분 함수로 빼서 구현하긴 했지만 대충 수도는 이렇게 되는거같다.

다른 사람의 풀이)

특히 비교하는 부분에서 코드가 매우 길어져서 다른 방법을 찾아봤다.

char a[7], char b[7]을 선언한다.

a - 두 수의 곱을 저장할 배열

b - 두 수의 곱을 역순으로 저장한 배열

sprintf(a, "%d", z); strcpy(b, a); _strrev(b);

strrev 문자열을 역순으로 저장하여 

strcmp(a, b) == 0

비교 함수를 통해 마무리.. 참 이렇게 몇 줄로 되는걸...

루비를 안 배워서 잘 모르겠지만 루비는 거의 6줄이면 이게 되던데...

알만툴에서 루비 사용한다던데 조금 궁금하긴 하다. 어떤 언어인지.

일단 지금은 유니티가 먼저니 C# 공부나 빡세게!!

여튼 이는 나와 같은 방법으로 구현한 알고리즘 중 결과를 도출해냈던 다른 방법이고,

전제에서 미리 예외를 찾아내 성능을 올리는 방법도 있었다.

만약 palindrome 수가 abccba라고 가정했을 때,

abccba = 100000a + 10000b + 1000c + 100c + 10b + a = 100001a + 10010b + 1100c.

이 값은 11로 묶을 수 있으며 11(9091a + 910b +100c)가 된다.

두 수 중 하나는 무조건 11의 배수임을 활용하면 성능을 훨씬 빠르게 할 수 있다.

아마 이 문제의 핵심이 아니었나한다.