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

✅ 예제 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

---

풀이

문제 자체를 이해하는데 좀 고생한 문제..
생성자가 존재하는 수, 생성자가 존재하지 않는 수(셀프 넘버) 어쩌구 하는데 뭔 말인가 싶었다.

구글링 좀 해보니 문제에 주어진 규칙을 적용할 수 없는 숫자가 바로 셀프 넘버라고 한다.

'아, 알겠는데.. 그래서 뭐 어쩌라는 거지?'싶을 수 있다. 다음 예시들을 보며 이해해보자.

🔎 생성자가 존재하는 경우
예를 들어 전달받은 값이 '1'이라고 하자. 규칙을 적용하면, 다음과 같은 결과가 나오게 된다.

1(전달받은 값) + 1(각 자리수) = 2(결과)

즉, 결과값인 '2'의 경우 생성자인 '1'(전달받은 값)이 존재하므로 셀프 넘버가 아닌 것이다.


🔎 생성자가 존재하지 않는 경우(셀프 넘버)
반면에 결과 값을 '3'이라고 가정해보자.

?(전달받은 값) + ?(각 자리수) = 3(결과)

이쯤해서 다시 규칙을 보자면,

양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수

그렇다. 결과값인 '3'의 경우, 일의 자리수이므로 전달 받은 값인 'n' 값과 'n'의 자리수를 더하여 '3'이 나와야 한다. 즉, n＋n = 3 이 식이 성립해야 하는 것이다.

그러나 식을 풀어보면 'n'은 정수가 아니라는 것을 알 수 있다. 이 말인 즉, 'n'은 생성자가 될 수 없다는 뜻이다. 생성자가 존재하지 않으므로 셀프 넘버인 것이다.

웬만하면 다 이해했으리라 믿어 의심치 않는다. 그렇다면 코드는 어떻게 짜야할까?

📃 메인 메소드

1. 생성자가 존재하는 숫자를 표시할 배열을 생성한다. 배열의 크기는 넉넉하게 100001으로 생성해준다.
2. 반복문을 통해 1부터 10,000까지 함수 d(n)으로 값을 전달하여 생성자로 생성한 숫자를 받아온다. 받아온 숫자의 위치에 생성자가 존재함을 표시한다.
3. 반복문을 통해 배열에 생성자의 존재여부를 확인한다. 만약 생성자가 존재하지 않는 숫자, 즉 셀프 넘버라면 출력한다.

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

1. 전달되어온 값의 각 자리수를 추출한다.
2. 변수를 하나 선언하여 전달되어온 값과 각 자리수를 더한 값을 저장한다.
3. 결과값을 리턴한다.
   
   

위와 같은 방식으로 짜면 된다. 밑에 바로 풀이가 있긴 하지만, 왠만하면 먼저 고심해보고 안 풀리면 보는 걸 추천한다.

💡 방법1 - 내 풀이

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int[] num = new int[100001];	// 생성자 존재 표시할 배열
		
		for(int i=1; i<=10000; i++) {	// 1부터 10000까지
			int n = d(i);	// 현재 제어변수 값을 전달하고 생성자로 생성한 숫자 받아오기
			num[n]++;	// 배열의 인덱스를 생성자가 존재하는 숫자로 지정하고 표시
		}
		
		for(int i=1; i<=10000; i++) {
			if(num[i]==0) {	// 셀프 넘버인 경우(생성자가 없는 숫자인 경우)
				bw.write(String.valueOf(i));
				bw.newLine();
			}
		}
		
		bw.flush();
		bw.close();
	}
	
	public static int d(int n) {
		int sum = n;
		String str = String.valueOf(n);	// 각 자리를 추출
		
		for(int i=0; i<str.length(); i++)
			sum += Character.getNumericValue(str.charAt(i));
		
		return sum;
	}
}

💡 방법 2 - 다른 사람 풀이 1

기본적으로 풀이 방법은 같고 다만 배열을 int 타입 말고 boolean 타입으로 선언하여 사용. (천재인줄..) 앞으로 비슷한 문제 나오면 그 때 써먹어야지~!

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		boolean[] num = new boolean[100001];
		
		for(int i=1; i<=10000; i++) {
			int n = d(i);
			num[n] = true;	// 생성자가 존재하는 값임을 표시
		}
		
		for(int i=1; i<=10000; i++) {
			if(!num[i]) { // 'num[i] == false' 와 같다
				bw.write(String.valueOf(i));
				bw.newLine();
			}
		}
		
		bw.flush();
		bw.close();
	}
	
	public static int d(int n) {
		int sum = n;
		String str = String.valueOf(n);
		
		for(int i=0; i<str.length(); i++)
			sum += Character.getNumericValue(str.charAt(i));
		
		return sum;
	}
}

💡 방법 2 - 다른 사람 풀이 2

각 자리수를 추출하는 부분에서 String 타입으로 변환하는 대신, 전달받은 값을 10으로 나누어 몫과 나머지를 구하여 리턴할 값을 구한다.

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		boolean[] num = new boolean[100001];
		
		for(int i=1; i<=10000; i++) {
			int n = d(i);
			num[n] = true;
		}
		
		for(int i=1; i<=10000; i++) {
			if(!num[i]) {
				bw.write(String.valueOf(i));
				bw.newLine();
			}
		}
		
		bw.flush();
		bw.close();
	}
	
	public static int d(int n) {
		int sum = n;

		while(n!=0){
 			sum += n%10;
 			n /= 10;
  		}
        
		return sum;
	}
}