[프로젝트 오일러] 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수 (Largest palindrome product)

4번째 프로젝트 오일러 문제입니다. (3번은 풀었으나, 손볼 곳이 조금 있는 관계로 나중에 포스팅하도록 하겠습니다.)

문제 전문은 아래와 같습니다.

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

코드를 작성함에 있어서 가장 기본적인 원칙은 아래와 같습니다.

1. clean code를 최대한 준수하도록 합니다. 
• 코드의 라인 수가 짧을 수록 좋겠지만 그것보다는 깨끗한 코드를 만드는데에 더 초점을 두었습니다.
• SRP(단일 책임 원칙), OCP(개방-폐쇄 원칙), 한 메소드 내에 동일한 추상화를 최대한 유지하도록 하였습니다.
• 하드코딩으로 특정 문제만 풀 수 있는 것이 아닌 모든 경우의 수를 해결할 수 있도록 하였습니다.
2. 1의 가독성이 유지되는 선에서 가능한한 코드를 짧게 합니다.
3. 언어는 Java를 사용합니다.
4. 테스트 주도 개발 기법(TDD, Test - Driven - Development)을 이용합니다.
5. 가능한한 혼자 힘으로 해결합니다.
• 막히는 부분이 있을때, 비효율적인 코드가 나올지라도 찾아보지 않고 혼자 힘으로 해결합니다. (이는 저의 프로그래밍 실력을 향상시키기 위한 프로젝트이기도 합니다.)
• 해당 수학적인 라이브러리가 구현되어 있다고 하더라도 기본적인 API 이외에는 스스로 구현합니다. 

※ 테스트 주도 개발 기법에 대하여 보다 자세히 알고 싶으시면 구글에 검색, 또는 제가 1년 전에 작성한 http://jhleed.tistory.com/13 을 참조하세요 :)

깃허브 주소 : https://github.com/jhleed/ProjectEuler/tree/largestPalindromeProduct

※ Palindrome : 대칭수,  Cipher : 자릿수

가장 간단한 테스트를 먼저 작성합니다.

1자리의 수를 곱해서 나올 수 있는 가장 큰 대칭수를 구해봅니다.

1자리의 수 중 가장 큰 값은 9이고, 따라서 1자리의 수를 서로 곱해서 나올 수 있는 가장 큰 값은 81입니다.

이중에 나올 수 있는 대칭수는 

9 11 22 33 44 55 66 77 가 있는데,  1자리의 수를 서로 곱하여 만들 수 있는 대칭수는 3 * 3 = 9 입니다.

가장 간단하게 통과시킵니다.

(1이 들어오면 9를 리턴한다)

다음은 다시 테스트 코드를 작성합니다.

두 번째로 간단한 테스트는 무엇일까요?

1자리를 테스트했으니 이번엔 2자리를 테스트해봅니다.

2자리 수를 곱해서 만들 수 있는 가장 큰 대칭수는?

고맙게도 예제에서 이미 주어져 있습니다. 

91 * 99 = 9009 입니다. 

이 역시 가장 간단하게 하드코딩으로 통과시킵니다.

2라는 자릿수가 들어오면 9009를 반환합니다.

여기에서 규칙을 찾을 수 있을까요?

아직 보이지 않습니다.

일단 리팩토링을 시작해봅니다.

반환값을 result라는 int형 변수에 담아서 반환하도록 합니다.

그러고보면 자릿수 2가 들어왔을때 반환되는 9009라는 값은 대칭수 (Palindrome)이군요.

result로 반환하기 전에 해당 값이 대칭수인지를 체크하는 과정이 필요 할 것 같습니다.

isPalindrome이라는 메소드를 생성해줍니다.

들어오는 값 9009가 대칭수인지를 판별하는 로직을 어떻게 작성할까요?

우선 하드코딩으로 일일히 작성해봅시다.

9009에서 0번째 자리(9)와 3번째 자리(9)가 같지 않으면 false,

1번째 자리(0)와 2번째 자리(0)이 같지 않으면 false를 리턴해야 합니다.

들어온 9009를 String "9009"로 변형하고, 0과 3번째 자릿수

1과 2번째 자릿수를 비교해줍니다.

조금 더 일반화를 시켜봅니다.

0과 3번째를 비교하기 위해 lastIndex를 구합니다. (전체 길이 - 1)

또한 전체 문자열의 절반만 서로 같으면 되므로 "9009"의 길이의 절반만 loop를 돌아줍니다.

그러면 아래와 같은 코드가 나오게 됩니다.

여기서 접근제한자를 private에서 protected로 바꾼 이유는 이 아래에 나오는 테스트코드를 작성하기 위함입니다.

isPalindrome이 제대로 동작하는지에 대한 검증이 필요하므로 역시 테스트코드를 만들어 줍니다.

여러개의 대칭수에 대한 검증이 모두 잘 통과하므로 대칭수를 검사하는 isPalindrome 메소드가 완성되었음을 검증할 수 있습니다.

다시 원래의 LargestPalindromeProduct 클래스로 돌아옵니다.

자릿수에 맞는 대칭수 중 가장 큰 값을 구하기 위해서 이렇게 로직을 타보기로 하죠.

1. 해당 자릿수로 만들 수 있는 대칭수를 모두 구한다.
2. 그 대칭수들 중 가장 큰 값을 구한다.

1번 : 대칭수를 모두 구한다 를 위해서는 List 자료구조가 있어야 할 것 같습니다.

List<Integer> palindrome을 선언해줍시다.

 다음으로는 2자리에서 만들 수 있는 대칭수들 중 4444가 있다고 가정하고, 4444와 9009를 모두 list에 add해줍니다.

이렇게 만들어진 List에서 가장 큰 값을 추출하여 반환하는 메소드를 만듭니다.

(getLargest 메소드)

테스트 코드를 돌려보니 현재까지 잘 동작합니다.

자, 지금까지 구현된 기능은 두가지입니다.

1. 숫자가 대칭수인지를 판별할 수 있음

2. 대칭수들 중 가장 큰 값을 구할 수 있음

여기에 2자리에서 뽑아낼 수 있는 모든 숫자를 구한다면 아래와 같은 로직을 탈 것이고, 그러면 문제가 해결될 것 같네요.

1. 자릿수에서 뽑아낼 수 있는 모든 숫자를 구할 수 있음

2. 숫자가 대칭수인지를 판별할 수 있음

3. 대칭수들 중 가장 큰 값을 구할 수 있음

아직 미구현인 1번 기능을 구현해봅시다.

2자리 중 제일 큰 숫자는 99입니다. 명백하죠

그러면 2자리로부터 도출될 수 있는 모든 숫자의 범위는 1부터 99 * 99가 됩니다.

모든 값을 구하려면, 2중 loop를 이용하여 99 * 99의 범위를 검사하면 되겠군요.

그러면 자릿수를 입력받아 해당 자릿수로부터 최대의 정수를 반환하는 메소드를 작성해봅시다.  

getMaxNumFromCipher를 일단 하드코딩으로 작성하고, 2중 loop를 작성합니다.

테스트코드는 잘 동작합니다.

 

2에 대해서는 잘 동작하는 솔루션인데, 이 솔루션은 1에 대해서도 잘 동작할까요?

1의 케이스에도 그대로 복사 붙여넣기를 해봅시다.

잘 동작합니다!

그렇다면 1자릿수와 2자릿수는 완전히 중복된 솔루션을 사용하고 있네요.

if와 중복을 제거해줍니다.

자.. 이제 1자릿수와 2자릿수에 대하여 일반화된 솔루션이 구현되었습니다.

아직 자릿수에서 최대의 정수를 뽑아내는 getMaxNumFromCipher 메소드는 하드코딩이지만요 =)

3자릿수에 대해서도 하드코딩을 해보도록 합니다.

3자리 수 중 최대의 정수값은 999입니다.

3자리 수를 하드코딩하고 아래 테스트 코드의 결과를 보니 906609라는 값이 나오는군요.

과연 이 값은 우리가 찾는 정답일까요?

.

.

.

네 정답입니다. 

뭔가 싱거운가요 ~??

하지만 아직 리팩토링이 끝나지 않았습니다.

하드코딩도 풀어야 하고, 가독성, 유지보수성을 위하여 코드를 개량하여야 합니다. ^^

이전의 코드를 보도록 하죠.

1자리 : 9

2자리 : 99

3자리 : 999

여기에서 규칙을 찾아낼 수는 없을까요?

우선 아래와 같이 나눠 봤습니다.

반환값을 result라는 Int형 변수에 담고, 아래와 같이 표현할 수도 있겠네요.

자 이제 일반화를 해보겠습니다. 

위의 코드는 다음 코드와 같이 일반화를 할 수 있습니다.

private int getMaxNumFromCipher(int cipher) {
    int result = 0;
    for(int i=0, addVal = 9;i<cipher; i++, addVal*=10){
        result += addVal;
    }
    return result;
}

리팩토링을 해줍시다. 

아래의 2중 loop에서는 각각 2번 maxNumFromCipher(cipher)을 호출해주고 있습니다.

동일한 결과를 반환하는 메소드를 2번 호출하는 것은 불필요한 오버헤드를 발생시키기 때문에

maxNumFromCipher라는 int형 변수에 담아줍니다.

다시 리팩토링을 해줍니다.

getLargestPalindromeByCipher메소드 내부에 있는 2중 Loop는 한 메소드 내에는 동일한 레벨의 추상화를 가져야 한다는 원칙을 깨뜨리기 때문에 별도의 메소드로 추출해줍니다 (extractPalindromes)

이렇게 해서 완성된 코드입니다.

지금 보니 변수명과 리팩토링을 할 여지가 많이 남아있긴 하군요 ^^

이것으로 프로젝트 오일러의 5번째 문제에대한 풀이를 마치도록 하겠습니다.

import java.util.ArrayList;
import java.util.List;

/**
 * Created by james on 15. 12. 16.
 */
public class LargestPalindromeProduct {
    public int getLargestPalindromeByCipher(int cipher) {
        int maxNumFromCipher = getMaxNumFromCipher(cipher);
        List<Integer> palindromes = extractPalindromes(maxNumFromCipher);
        return getLargest(palindromes);
    }

    private List<Integer> extractPalindromes(int maxNumFromCipher) {
        List<Integer> palindromes = new ArrayList<Integer>();
        for(int i=1;i<= maxNumFromCipher;i++){
            for(int j=1;j<= maxNumFromCipher;j++){
                if(isPalindrome(i*j)){
                    palindromes.add(i*j);
                }
            }
        }
        return palindromes;
    }

    private int getMaxNumFromCipher(int cipher) {
        int result = 0;
        for(int i=0, addVal = 9;i<cipher; i++, addVal*=10){
            result += addVal;
        }
        return result;
    }

    private int getLargest(List<Integer> palindromes) {
        int result = 0;
        for(int val : palindromes){
            if(result < val){
                result = val;
            }
        }
        return result;
    }

    protected boolean isPalindrome(int intNumber) {
        String strNumber = Integer.toString(intNumber);
        int lastIndex = strNumber.length() - 1;
        for(int index=0;index<strNumber.length()/2;index++){
            if(strNumber.charAt(index)!=strNumber.charAt(lastIndex-index)){
                return false;
            }
        }
        return true;
    }
}