알고리즘 - 완전탐색 - 재귀

최초 23/12/10

https://www.acmicpc.net/problem/4673

문제 요약

d(n): n + n의 모든 자리수의 합
ex)d(75) = 75 + 7 + 5 = 87
ex)d(1) = 1 + 1 = 2
ex)d(2) = 2 + 2 = 4
셀프넘버: n > 0 인 어떤 n에 대해서도 d(n)이 자신이 되지 않는 수
ex)1, 3, 5, ...
1에서 10,000 범위 안의 셀프넘버를 한줄 씩 출력

준비물

연산자 관련: %
자료형 관련: HashSet.add(), HashSet.remove()
문법 관련: static inner class
알고리즘 관련: recursive 함수
디버깅 관련: 메모장에 예제 쓰는 습관

구현

import java.util.Set;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        SimpleNums simpleNums = new SimpleNums();

        simpleNums.setMax(10000);

        for (int i = 1; i <= 10000; i++) {
            simpleNums.makeNum(i);
        }

        simpleNums.print();
    }

    private static class SimpleNums {
        private final Set<Integer> simpleNums = new HashSet<>();

        private void setMax(int max) {
            for (int i = 1; i <= max; i++) {
                simpleNums.add(i);
            }
        }

        private void print() {
            for (Integer num : simpleNums) {
                System.out.println(num);
            }
        }

        private void makeNum(int input) {
            int num = input;
            num += makeSum(input);

            if (num > 10000) {
                return;
            }
            if (simpleNums.remove(num)) {
                return;
            }

            makeNum(num);
        }

        private int makeSum(int input) {
            if (input <= 0) {
                return 0;
            }

            int quo = input / 10;
            int rem = input % 10;

            return rem + makeSum(quo);
        }
    }
}