알고리즘 단계별로 풀어보기 : BOJ-4673(셀프넘버)

문제(출처)

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 

양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 

예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 

이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 

위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 

생성자가 한 개보다 많은 경우도 있다. 

예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 

100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다.

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

예제 입력

예제 출력

1

3

5

7

9

20

31

42

53

64

 |

 |       <-- a lot more numbers

 |

9903

9914

9925

9927

9938

9949

9960

9971

9982

9993

내 풀이

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.OutputStreamWriter;

public class Main{

    public static void main(String args[]) {

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        /*

         * 9까지는 2씩 증가 9부터 11 증가 : 정답과 결과 값이 다르다. 규칙이 있을까 해서 확인해 봤다.

         */

        /*

         * for(int i = 20; i < 10000; i+=11) { try { bw.write(String.valueOf(i));

         * bw.newLine(); } catch (IOException e) { // TODO Auto-generated catch block

         * e.printStackTrace(); } }

         */

        int[] noSelfNum = new int[10000];

//      구하고자 하는 양만큼의 배열을 선언했다.

        

        int check = 0;

//      셀프 넘버가 아닌 숫자를 저장한다.

        for (int i = 0; i < noSelfNum.length; i++) {

//          구하고자 하는 양만큼 1씩 증분하여 반복한다.

            check = noSelfNumber((i+1), (i+1));

//          재귀함수를 호출하여 셀프 넘버가 아닌 숫자를 구하고 check변수에 저장한다.

//            1부터 시작하므로 i에 1을 더해준다

            if(noSelfNum.length > check) {

//              셀프 넘버가 아닌 숫자가 구하고자 하는 양을 넘었는지 체크한다.

                noSelfNum[check] = -1;

//              넘지 않았다면 셀프 넘버에 -1을 입력한다. 이는 셀프 넘버가 아닌 배열의 위치를 기록한다.

            }

        }

        for (int i = 1; i < noSelfNum.length; i++) {

//          1부터 구하고자 하는 숫자의 양만큼 1씩 증분하여 반복한다.

            try {

                if(noSelfNum[i] != -1) {

//                  배열에서 -1이 입력 된 값이 아닌 값을 확인하고 출력한다.

                    bw.write(String.valueOf(i));

                    bw.newLine();

                }

                    

            } catch (IOException e) {

                // TODO Auto-generated catch block

                e.printStackTrace();

            }

        }

        try {

            bw.flush();

            bw.close();

        } catch (IOException e) {

            // TODO Auto-generated catch block

            e.printStackTrace();

        }

    }

    public static int noSelfNumber(int number, int sum) {

//      셀프 넘버가 아닌 숫자를 호출하는 재귀 함수이며

//        number은 연산해야 하는 변수, sum은 더해야 하는 변수이다.

//      ex) 125 : 125/10=12 125%10=5 -> (재귀 호출) 12/10=1 12%10=2 -> (재귀호출) 1/10=0 1%10=1

//                      sum = 125 + 5           sum = 130 + 2           sum = 132 + 1

        int tan = 0;

//      10의 자리를 저장한다.

        int one = 0;

//      1의 자리를 저장한다.

        tan = number / 10;

//      입력 받은 수를 나누어 10의 자리를 구하여 저장한다.

        one = number % 10;

//      입력 받은 수의 나머지인 1의 자리를 구하여 저장한다.

        sum += one;

//      누적되는 값을 가지고 있는 sum 변수와 1의 자리를 더한다.

        if(tan !=0) {

//          10의 자리가 0이 아니라면 재구 함수를 호출한다.

            return noSelfNumber(tan, sum);

//          10의 자리가 1이 될 때까지 반복해야 하므로 number 대신 tan을 넣어준다.

        }

        return sum;

//      누적 값을 반환한다.

    }

    

//  완성 되지 않은 코드이다.

//  1. 셀프넘버가 아닌 숫자를 찾는다.

//  2. 1-100까지 숫자 중에서 셀프 넘버가 아닌 숫자를 찾아서 제거한다.

//  3. 남은 셀프 넘버 숫자만 출력한다.

//  1-3번 순으로 개발 하려고 만든 함수이지만

//  애초에 셀프 넘버가 아닌 숫자를 표시하고 출력 하면 된다고 생각을 바꾸고 위에처럼 풀었다.

    /*public static int SelfNumber(int[] noSelfNum) {

        int[] checkNum = new int[100];

        int[] SelfNum = new int[100];

        int checkNumI = 0;

            for(int i = 0; i < noSelfNum.length; i++){

                if(noSelfNum[i] != i) {

                    checkNum[i] = i;

                    checkNumI++;

                }

            }

        return 0;

    }*/

}

내 풀이 해석

주석 참조

오래 걸렸다.(90분)

문제를 읽고 재귀함수로 풀어야 하는 문제구나라고 생각이 들었습니다.

일정한 규칙으로 누적하여 합을 구하는 문제입니다.

일정한 규칙으로 구한 값을 스택에 저장에 해서 양파까듯 하나씩 꺼내 합하는 방식입니다.

구하고자 하는 숫자만큼 배열을 생성합니다.

10의 나눗셈과 10의 나머지를 이용하여 재귀함수를 만들어 10의 나눗셈이 0이 될때까지 반복합니다.

구한 값은 셀프 넘버가 아니므로 배열에 -1로 표시합니다.

이를 완료하면 배열에서 -1이 아닌 숫자를 출력합니다.

아쉬운 점

문제에 대한 이해는 빨랐지만 해결하는 방법을 고민하는데 시간을 많이 사용했습니다.

이중 반복문은 사용하고 싶지 않아 재귀함수로 풀었습니다.

재귀함수는 스택오버플로우가 발생할 수 있고 성능에 좋지 않은 방법으로 알고 있습니다.

다른 방법이 없나 찾아보았고 넥슨에서 제일 쉬운 문제로 제출했다고 합니다.