프로젝트 오일러 :: 04번 문제풀이 :: java

문제

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

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

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

풀이

필자 개인적으로는 매우 재미있는 문제라고 생각한다.

방법은 많겠지만 필자는 아래와 같은 순서로 문제를 풀고자 했다.

1.  해당 숫자가 대칭수인지 확인하는 함수를 작성
2. 100~999 숫자의 곱의 모든 조합을 확인
3.  곱의 조합 중 가장 큰 대칭수를 출력

대칭수는 앞으로 읽어도, 뒤로 읽어도 같은 모양인 숫자를 말한다.

어떤 숫자 x 가 대칭수인지 확인하기 위해서는 해당 숫자를 뒤집은 y를 구한 뒤 x == y 를 확인해야한다.

Array를 만들어 양 끝점부터 확인하는 방법, x를 String으로 변환해 뒤집은 뒤 문자열이 같은지 확인하는 방법 등 여러가지 방법이 있지만 필자는 수학 연산을 통해 구현해보기로 했다.

방법은 아래와 같다.

1. 숫자 x가 몇자리 수인지 파악.
2. x % 10 을 통해 1의자리 숫자 추출
3. 추출한 순서와 역순으로 숫자를 배치
4. 두 숫자가 같은지 비교

위 방법을 토대로 아래와 같이 함수를 작성했다.

public boolean isSymmetryNumber(int arg) {

     int digit = numOfDigit(arg);

     int originNum = arg;

     int symmetryNum = 0;

     int powCnt = digit - 1;

     for (int i = 0; i < digit; i++) {

           symmetryNum += (arg % 10) * Math.pow(10, powCnt);

           arg /= 10;

           powCnt--;

     }

     if (originNum == symmetryNum)

           return true;

     else

           return false;

}

public int numOfDigit(int arg) {

     int numOfDigit = 1;

     if (arg < 10)

           return numOfDigit;

     else {

           while (true) {

                arg /= 10;

                numOfDigit++;

                if (arg < 10)

                     return numOfDigit;

           }

     }

}

함수 설명은 아래와 같다.

• public int numOfDigit(int arg) : 숫자의 자릿수를 반환
• public boolean isSymmetryNumber(int arg) : 숫자가 대칭수인지 여부 반환

-

이제 대칭수를 구할 수 있게 됐으니 답을 구하는 알고리즘을 구현해보자.

방법은 단순하다.

이중 반복문을 통해 100부터 999까지의 모든 곱의 조합을 구한 뒤, 해당 수가 대칭수이면 그 값을 저장하고 제일 큰수를 찾으면 된다.

public void solution() {

     int arg1 = 999, arg2;

     int result = 0;

     int tmp;

     while (true) {

           arg2 = arg1;

           for (int i = 0; i < arg1; i++) {

                tmp = arg1 * arg2;

                if (tmp % 10 == tmp / (int) Math.pow(10, numOfDigit(tmp) - 1) && result < tmp) {

                     if (isSymmetryNumber(tmp)) {

                           result = tmp;

                           System.out

                                     .println("current biggest symmetry number is " + result + " = " + arg1 + " * " + arg2);

                     }

                }

                arg2--;

                if (arg2 < 100)

                     break;

           }

           arg1--;

           if (arg1 == 0 && arg1 < 100)

                break;

     }

}

999부터 1씩 감소시키며 답을 구하도록 로직을 구현했다.

단, 아래와 같이 2가지 조건을 만족하는 경우에만 대칭수인지의 여부를 파악하도록 했다.

1. 해당 숫자의 첫번째 숫자와 마지막 숫자가 같은 경우
2. 두 세 자릿수 숫자의 곱이 기존에 저장한 대칭수보다 큰 경우

이러한 조건은 불필요한 연산을 줄여주며 결과 도출까지의 시간을 단축시켜준다.

필자의 solution의 경우, 조건문의 유무에 따라 process 시간이 100ms나 차이났다.

-

위 solution을 실행시키면 아래와 같은 결과를 얻을 수 있으며 문제의 정답이다.

~ Epilogue ~

방법은 단순하지만 필요한 함수를 작성하고 이중포문 및 조건문을 활용해 답을 도출하는 과정이 재밌었다.

혹시 필자의 코드 중 이해가 되지 않는 부분이 있으면 댓글을 남겨주기 바란다.

github