[백준 4673번/JAVA] 셀프 넘버

문제

셀프 넘버는 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다. 

---

 

d(n)은 n과 n의 각 자리수를 더하는 함수

n, d(n), d(d(n)), ...

위와 같은 수열에서 생성자가 없는 숫자를 셀프 넘버라고 함

 

 

문제를 풀어보기에 앞서 감을 잡기 위해 d(75)의 예시를 손으로 직접 작성해보았다.

 

주어진 입력은 없고 출력은 10000보다 작거나 같은 셀프 넘버이다.

수의 범위가 작으니 배열을 만들어서 셀프 넘버의 가능성이 없는 수를 하나씩 지워가며 풀었다.

 

코드는 다음과 같은 순서로 작성하였다.

1. 배열 생성 (isSelfNum 배열은 boolean 타입)

2. 셀프 넘버 아닌 수 지우기 (별도 함수 작성)

3. 셀프 넘버 출력

 

2번의 셀프 넘버 아닌 수를 지우는 로직이 이 문제의 핵심인거 같다. 

생성자 i를 입력 받아 i를 시작으로 수열을 만든다.

수열에 해당되는 숫자는 i를 생성자로 갖기 때문에 셀프 넘버가 될 수 없다.

   // 생성자를 받아 수열을 만들며 배열에 false 표시 해주는 메소드
    static void markNonSelfNum(int i) {
        int sum;
        int j;

        while(true){    // i값 업데이트
            sum = i;
            j = i;

            while(j > 0){       // j값 업데이트, 수열의 다음 수 구하는 코드
                sum += j % 10;
                j /= 10;
            }

            if(sum > 10000)
                break;

            isSelfNum[sum] = false;
            i = sum;
        }
    }

 

재귀로도 가능할거 같은데 기회가 된다면 재귀로도 풀어보고 싶다.

아래는 코드 전문이다.

import java.util.Arrays;

public class BJ4673 {

    static boolean[] isSelfNum;

    public static void main(String[] args) {
        // 1. 배열 생성
        isSelfNum = new boolean[10001];
        Arrays.fill(isSelfNum, true);

        // 2. 셀프넘버 아닌 수 지우기
        for (int i = 1; i <= 10000; i++) {
            if(isSelfNum[i])
                markNonSelfNum(i);
        }

        // 3. 셀프넘버 출력
        StringBuilder result = new StringBuilder();
        for (int i = 1; i <= 10000; i++) {
            if(isSelfNum[i])
                result.append(i + "\n");
        }
        System.out.println(result);
        
    }

    // 생성자를 받아 수열을 만들며 배열에 false 표시 해주는 메소드
    static void markNonSelfNum(int i) {
        int sum;
        int j;

        while(true){    // i값 업데이트
            sum = i;
            j = i;

            while(j > 0){       // j값 업데이트
                sum += j % 10;
                j /= 10;
            }

            if(sum > 10000)
                break;

            isSelfNum[sum] = false;
            i = sum;
        }
    }
}

 

:)

 

친구의 피드백: j는 필요없다. 친구 말이 틀리길 바랬지만 진짜 j는 필요 없었다.