[알고리즘] 백준 4673 셀프 넘버 Java

https://www.acmicpc.net/problem/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

1
3
5
7
9
20
31
42
53
64
|
| <-- a lot more numbers
|
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

Code

import java.util.HashSet;

public class Main {

    public static int d(int number){
        int temp = number;
        while( number != 0){
            temp = temp + number % 10;
            number = number / 10;
        }
        return temp;
    }

    public static void main(String[] args) {

        int num =1;

        HashSet<Integer> hashSet = new HashSet<>();


        for(int i = 1; i < 10001; i++){
            int n = d(i);

            if( n <10000){
                hashSet.add(n);
            }

        }

        for(int i = 1; i < 10000; i++){
            if(!hashSet.contains(i)){
                System.out.println(i);
            }
        }
    }
}

Point

드디어 실버문제이다.

d(int number) 라는 메서드는 각 자릿수를 구해서 number값에 더해주는 메서드이고,
main 메서드에서 HashSet을 이용해서 중복을 제거하고 d()메서드를 통해 return 받은 값을 모두 저장 시켜준다.
HashSet을 사용한 이유는 문제에 나와있듯이 101의 경우 2개의 생성자를 갖기때문에 중복이 많이 발생되기 때문이다.

그렇게 하여 for문을 이용하여 HsahSet값에 i값이 포함되지 않았다면 그 i값은 셀프넘버이기 때문에 그 값들을 반복문으로 출력해 주었다.