[코딩 도장] 넥슨 입사문제 중에서

이번 주는 코딩 도장(http://codingdojang.com/) 사이트에서 넥슨 입사 문제 중 하나로 아래와 같은 문제가 있어 풀어보았다.

어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 + 91 = 101 이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1, 3, 5, 7, 9, 20, 31 은 셀프 넘버 들이다. 1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.

알고리즘은 아래와 같다.

1. 1~5000까지 제너레이터 숫자를 모두 구한다.
2. 1~5000까지 제너레이터 숫자를 제외하고 모두 합한다.

간단하지만 모든 수를 한 번씩 다 체크해야 하기 때문에 좋은 성능이라고 이야기하기 어려울 것 같다.

구현은 자바로 하였으며, Map, Set, List 등의 Collection 객체를 사용하지 않고 구현하였다. 만약 사용한다면 조금 더 쉽게 구현할 수 있을 것이다.

public class SelfNumber {     public int sumUpSelfNumber(int from, int to) {         if (from > to) {             return 0;         }         boolean[] generatorNums = new boolean[to - from + 1];         Arrays.fill(generatorNums, false);         for (int i = from; i < to + 1; i++) {             int generatedNum = getGeneratedNum(i);             if (generatedNum <= to) {                 generatorNums[generatedNum - from] = true;             }         }         int sum = 0;         for (int i = 0; i < generatorNums.length; i++) {             if (generatorNums[i] == false) {    //self-number                 System.out.print(String.format("%d ", i + from));                 sum = sum + (i + from);             }         }         System.out.println();         return sum;     }     private int getGeneratedNum(int num) {         int sum = num;         while (num > 0) {             sum = sum + num%10;             num = num/10;         }         return sum;     } }

public class SelfNumberTest {     @Parameterized.Parameters     public static Collection<Object[]> parameters() {         return Arrays.asList(new Object[][]{                 {1, 10, 25},                 {1, 31, 76},                 {1, 5000, 1227365}         });     }     private int from;     private int to;     private int sum;     public SelfNumberTest(int from, int to, int sum) {         this.from = from;         this.to = to;         this.sum = sum;     }     private SelfNumber selfNumber = new SelfNumber();     @Test     public void SelfNumber_테스트() {         int result = selfNumber.sumUpSelfNumber(this.from, this.to);         assertEquals(sum, result);     } }

TC를 수행해 보면 정상적으로 수행이 된다.

self-number 에는 어떤 수들이 있는지 출력해 보았다.

1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468 479 490 501 512 514 525 536 547 558 569 580 591 602 613 615 626 637 648 659 670 681 692 703 714 716 727 738 749 760 771 782 793 804 815 817 828 839 850 861 872 883 894 905 916 918 929 940 951 962 973 984 995 1006 1021 1032 1043 1054 1065 1076 1087 1098 1109 1111 1122 1133 1144 1155 1166 1177 1188 1199 1210 1212 1223 1234 1245 1256 1267 1278 1289 1300 1311 1313 1324 1335 1346 1357 1368 1379 1390 1401 1412 1414 1425 1436 1447 1458 1469 1480 1491 1502 1513 1515 1526 1537 1548 1559 1570 1581 1592 1603 1614 1616 1627 1638 1649 1660 1671 1682 1693 1704 1715 1717 1728 1739 1750 1761 1772 1783 1794 1805 1816 1818 1829 1840 1851 1862 1873 1884 1895 1906 1917 1919 1930 1941 1952 1963 1974 1985 1996 2007 2022 2033 2044 2055 2066 2077 2088 2099 2110 2112 2123 2134 2145 2156 2167 2178 2189 2200 2211 2213 2224 2235 2246 2257 2268 2279 2290 2301 2312 2314 2325 2336 2347 2358 2369 2380 2391 2402 2413 2415 2426 2437 2448 2459 2470 2481 2492 2503 2514 2516 2527 2538 2549 2560 2571 2582 2593 2604 2615 2617 2628 2639 2650 2661 2672 2683 2694 2705 2716 2718 2729 2740 2751 2762 2773 2784 2795 2806 2817 2819 2830 2841 2852 2863 2874 2885 2896 2907 2918 2920 2931 2942 2953 2964 2975 2986 2997 3008 3023 3034 3045 3056 3067 3078 3089 3100 3111 3113 3124 3135 3146 3157 3168 3179 3190 3201 3212 3214 3225 3236 3247 3258 3269 3280 3291 3302 3313 3315 3326 3337 3348 3359 3370 3381 3392 3403 3414 3416 3427 3438 3449 3460 3471 3482 3493 3504 3515 3517 3528 3539 3550 3561 3572 3583 3594 3605 3616 3618 3629 3640 3651 3662 3673 3684 3695 3706 3717 3719 3730 3741 3752 3763 3774 3785 3796 3807 3818 3820 3831 3842 3853 3864 3875 3886 3897 3908 3919 3921 3932 3943 3954 3965 3976 3987 3998 4009 4024 4035 4046 4057 4068 4079 4090 4101 4112 4114 4125 4136 4147 4158 4169 4180 4191 4202 4213 4215 4226 4237 4248 4259 4270 4281 4292 4303 4314 4316 4327 4338 4349 4360 4371 4382 4393 4404 4415 4417 4428 4439 4450 4461 4472 4483 4494 4505 4516 4518 4529 4540 4551 4562 4573 4584 4595 4606 4617 4619 4630 4641 4652 4663 4674 4685 4696 4707 4718 4720 4731 4742 4753 4764 4775 4786 4797 4808 4819 4821 4832 4843 4854 4865 4876 4887 4898 4909 4920 4922 4933 4944 4955 4966 4977 4988 4999

뭔가 특이한 점을 발견할 수 있다.

10 이하의 수의 홀수는 self-number 일 수 밖에 없다. 그 이유는 어떤 두 수를 더해서 홀수가 될 수 있는 방법은 없기 때문이다.(1자리 수는 자신을 두 번 더하기 때문)

10 이하의 마지막 self-number 부터는 특이한 성질이 있다.

9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 ...

9부터 9번의 11씩 증가와 1번의 2씩 증가를 계속해서 반복한다.

왜 9번의 11씩 증가와 1번의 2씩 증가를 반복할까?

이 규칙은 1000의 자리 10000의 자리에서도 유효할까?

102225까지 self-number는 다음 링크에서 확인할 수 있다.

https://oeis.org/A003052/b003052.txt

기본적으로 아래와 같은 3가지 규칙이 있는 듯하다.

• 10 이하의 수(1자리 수)에서는 홀수
• 2자리 수 이상부터는 이전 self-number에서 11씩 9번 증가, 2씩 1번 증가를 반복
• 단, 자리 수가 변경하는 시점에는 2 -> 15 -> 28 -> 41 순으로 증가량이 13씩 증가

어떤 원리가 있는 것인지 이해가 되지 않는다.

일단 wikipedia에서 self-number를 검색해 보았다.(https://en.wikipedia.org/wiki/Self_number)

위와 같이 수식으로 소개하고 있다.

뭔가 심오해 보이긴 하나. n에 대한 generator 숫자를 구해 보고 그 수가 없다면 n은 self-number라고 판단하는 수식이다.

이는 수식이 좀 복잡해 보이긴 하나 위에서 풀었던 알고리즘보다 나아 보이진 않는다. 일단 .구현해 보자

아래 코드는 기본적으로 위 수식을 기반으로 성능을 위한 약간의 개선 포인트들이 적용된 코드이다.

이는 함께 스터디하는 동료가 작성한 코드로 https://github.com/KimMinJoo/AlgorithmStudy/blob/master/src/main/java/com/naver/nexon/SelfNumber.java 에서 가져왔다.

public class SelfNumber {         private int range;         public SelfNumber(){}         public SelfNumber(int range) {                 this.range = range;         }         public void printSelfNumber() {                 printSelfNumber(range);         }         public void printSelfNumber(int range) {                 boolean[] selfNumberFlagArray = getSelfNumberFlagArray(range);                 for (int i = 1; i < selfNumberFlagArray.length; i++) {                         if (selfNumberFlagArray[i] == false) {                                 System.out.println(i);                         }                 }         }         private boolean[] getSelfNumberFlagArray(int range) {                 boolean[] selfNumberFlagArray = new boolean[range+1];                 for (int i = 0; i <= selfNumberFlagArray.length; i++) {                         int generatorNumber = calculateGenerator(i);                         if (generatorNumber >= selfNumberFlagArray.length) {                                 continue;                         }                         selfNumberFlagArray[generatorNumber] = true;                 }                 return selfNumberFlagArray;         }         private int calculateGenerator(int targetNumber) {                 int sum = targetNumber;                 int cipher = (int)Math.log10(targetNumber);                 for (int i = 0; i <= cipher; i++) {                         sum += targetNumber%10;                         targetNumber /= 10;                 }                 return sum;         }         public int getGeneratorNumber(int targetNumber) {                 int minPossipleNumber = getMinPossibleNumber(targetNumber);                 int minCipher = (int)Math.log10(minPossipleNumber);                 int minNumber = 0;                 for (int i = 1; i <= minCipher; i++) {                         minNumber += minPossipleNumber/(int)Math.pow(10, i);                 }                 int maxCipher = (int)Math.log10(targetNumber);                 int maxNumber = 0;                 for (int i = 1; i <= maxCipher; i++) {                         maxNumber += targetNumber/(int)Math.pow(10, i);                 }                 for (int i = minNumber; i <= maxNumber; i++) {                         int generatorNumber = (targetNumber + (9 * i)) / 2;                         int generator = calculateGenerator(generatorNumber);                         if (generator == targetNumber) {                                 return generatorNumber;                         }                 }                 return -1;         }         private int getMinPossibleNumber(int targetNumber) {                 int cipher = (int)Math.log10(targetNumber);                 int maxDistinct = 9*cipher + targetNumber/(int)Math.pow(10,cipher);                 return targetNumber - maxDistinct;         } }

generator 숫자를 찾기 위해 체크해야 할 숫자 범위를 줄이고자 하는 노력이 보인다.

그럼에도 첫 번째 방법보다는 체크해야 하는 범위의 숫자가 더 많기 때문에 성능은 조금 더 느릴 거 같다.

결론

수의 범위가 넓지 않다면 첫 번째 방법이 좋다고 생각한다. 좀 더 효율적인 방법이 있는지는 잘 모르겠다.

github: https://github.com/tomining/AlgorithmStudy/blob/master/src/main/java/com/algorithm/coding/dojang/SelfNumber.java

TC: https://github.com/tomining/AlgorithmStudy/blob/master/src/test/java/com/algorithm/coding/dojang/SelfNumberTest.java

---

참고

• http://codingdojang.com/scode/365?answer_mode=hide
  
• https://en.wikipedia.org/wiki/Self_number
  
• https://oeis.org/A003052