[백준 #4673] 셀프 넘버

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
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.util.Arrays;

public class Main {
	//1부터 10000사이 셀프 넘버 찾기
	
	//시도1 : 셀프 넘버가 아닌 애들을 찾고 제외한 수들을 최종 출력
	//이미 셀프넘버가 아님이 증명된 수는 중간에서 멈추기
	
	static boolean isSelfNumber[] = new boolean[10001]; // 1부터 10000까지 만약 d() 함수에서 결과가 나오면 false로 저장
	
	public static void d(int i, boolean start) {
		if(i > 10000) return;
		if(isSelfNumber[i] == false) return;
		
		if(start == false) isSelfNumber[i] = false; // 첫 시작 숫자를 제외하고 반영.
		
		int sum = i;
		while(i > 0) {
			sum += i % 10;
			i /= 10;
		}
		
		d(sum, false);
		
	}
	
	public static void main(String args[]) {
		
		Arrays.fill(isSelfNumber, true);
		
		for(int i=1; i<=10000; i++) {
			d(i, true);
		}
		
		
		isSelfNumber[1] = true; 
		StringBuffer sb = new StringBuffer();
		for(int i=1; i<=10000; i++) {
			if(isSelfNumber[i] == true) sb.append(i).append("\n");
		}
		
		System.out.println(sb);
	}

}

 

이 문제는 완전탐색(Brute Force) 방식으로 셀프 넘버가 아닌 수를 찾고 결과적으로 제외된 수들을 셀프 넘버로 간주하여 출력하도록 하는 구현문제이다.

 

 

 

---

로직 분석 (완전탐색 + 재귀 탐색)

 

1. 완전탐색의 개념

• 완전탐색(Brute Force): 가능한 모든 경우를 직접 확인하여 정답을 찾는 방식

• 이 코드에서의 완전탐색 요소

• 1부터 10,000까지 모든 숫자에 대해 d(n)을 구함

• d(n)을 계속 호출하면서 생성자가 존재하는 모든 수를 제거

 

2. 전체적인 흐름

1. isSelfNumber 배열을 true로 초기화

2. 1부터 10,000까지 모든 수에 대해 완전탐색 진행

3. 각 숫자의 생성자 수열을 계산(d(n))하여 셀프 넘버가 아닌 수를 false로 설정

4. 남아 있는 true인 숫자(셀프 넘버)를 출력

 

 

 

---

자료구조 분석

 

boolean isSelfNumber[10001] (크기 O(n))

• 완전탐색 시 필요한 메모리를 O(n)으로 유지

• true: 셀프 넘버 후보

• false: d(n)의 결과로 등장한 숫자(셀프 넘버 X)

 

StringBuffer (출력 최적화)

• 여러 개의 숫자를 System.out.println 대신 한 번에 출력하여 성능 향상

 

 

 

---

알고리즘 분석 (완전탐색 + 재귀)

 

1. d(n) 함수 (생성자 수열 계산)

public static void d(int i, boolean start) {
    if (i > 10000) return;
    if (!isSelfNumber[i]) return; // 이미 생성자로 등장한 경우 종료

    if (!start) isSelfNumber[i] = false; // 첫 시작 숫자가 아닌 경우 false 처리

    int sum = i;
    while (i > 0) {
        sum += i % 10;
        i /= 10;
    }

    d(sum, false);
}

 

• n에서 각 자리 숫자를 분해하여 d(n)을 계산 (자리수 합)

• 결과 sum을 이용해 재귀 호출 (d(sum))

• sum이 10000을 넘어서면 종료

 

---

 

2. 메인 함수 (완전탐색 수행)

public static void main(String args[]) {
    Arrays.fill(isSelfNumber, true); // 셀프 넘버가 아닌 수는 추후에 모두 false로 갱신됨

    for (int i = 1; i <= 10000; i++) {
        d(i, true); // 완전탐색 수행
    }

    StringBuffer sb = new StringBuffer();
    for (int i = 1; i <= 10000; i++) {
        if (isSelfNumber[i]) sb.append(i).append("\n");
    }

    System.out.println(sb);
}

 

• 1부터 10,000까지 모든 숫자에 대해 d(n)을 수행하는 완전탐색

• d(n)을 호출하면서 isSelfNumber 배열을 갱신

 

 

 

---

시간 복잡도 분석

 

1. 각 숫자 n에 대해 d(n) 계산 (자리수 합 연산)

• O(log n)

• n=9999일 때 최대 4자리 (9+9+9+9 계산)

• 4번의 연산 수행 (O(4) ≈ O(1))

 

2. 1부터 10,000까지 모든 수에 대해 d(n) 계산

• 10,000 * O(log n) ≈ O(n log n)

 

3. 최적화 가능성

• 중복 호출을 줄이면 O(n)까지 최적화 가능

• 반복문으로 변경하면 스택 오버플로우 방지

 

 

 

---

개선된 코드 (반복문 사용)

import java.util.Arrays;

public class Baekjoon4673 {
    static boolean isSelfNumber[] = new boolean[10001];

    public static int d(int n) {
        int sum = n;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        Arrays.fill(isSelfNumber, true);

        for (int i = 1; i <= 10000; i++) {
            int num = d(i);
            while (num <= 10000 && isSelfNumber[num]) {
                isSelfNumber[num] = false;
                num = d(num);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= 10000; i++) {
            if (isSelfNumber[i]) sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}

 

• 반복문 사용 → 재귀 호출 제거

• 중복 계산 방지 → while 문을 사용하여 d(n) 반복 수행

• 성능 향상 → O(n log n) → O(n)로 최적화