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

 

나의 풀이

못 풀었다. 다른 사람 풀이를 보고 바로 만들었다. 머리가 잘 안 돌아 갔다... 생성자와 그로 인한 수를 만드는 함수는 만들었는데 셀프 넘버는 어떻게 뽑아내지...? 의문이었다.
함수를 구현해 문제를 푸는 것에는 완전 초보라, 변수의 스코프가 어떻게 영향을 끼치는지도 애매하고 main 함수 위에다가 함수를 정의하나? 어떻게 하나? 쓸데없는 생각을 너무 많이 했다.

풀이는 간단했다. 셀프 넘버는 똑같은 크기의 불리언 배열을 선언해서, 인덱스 넘버를 이용해 생성자가 없는 셀프 넘버를 출력한다. 원리를 알고 나니 간단 명쾌하다!

package baekjoonOnlineJudge;

public class Bj_4673 {

	public static boolean[] hasGenerator = new boolean[10036];
	
	public static int selfSum(int n) {
		int sum = 0;
		String[] arrayN = Integer.toString(n).split("");
		
		for(int i=0; i<arrayN.length; i++) {
			sum += Integer.parseInt(arrayN[i]);
		}
		
		sum += n;
		hasGenerator[sum] = true;
		return sum;
	}

	public static void main(String[] args) {
		for(int i=1; i<10000; i++) {
			selfSum(i);
		}
		
		for(int i=1; i<10000; i++) {
			if(hasGenerator[i]==false) {
				System.out.println(i);
			}
		}
	}
}

참고한 다른 사람 풀이(https://hongku.tistory.com/233)