[Java] Java 연습문제: Self Number 탐색 프로그램

문제:

어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자.

예를 들어

d(91) = 9 + 1 + 91 = 101

이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다.

어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.

1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.

출처: codingdojang.com/scode/365?answer_mode=hide

 

Idea:

1. generator, n은 항상 d(n)보다 작기 때문에, 1부터 5000까지의 모든 자연수를 generator n로 취급하여 5000개의 d(n)을 구한다.

2. d(n)을 구할 때, 각 자릿 수의 합은 (int -> string -> 여러개의 char -> 여러개의 int)의 과정을 거친 결과인 여러개의 int와 n 자신을 더하여 d(n)을 만든다.

3. 위에서 구한 d(n)을 HashSet set에 저장한다. <- d(n)은 중복된 수가 많아서 깔끔하게 정리하기 위함.

4. 1부터 5000까지의 모든 수를 가지고 있는 HashSet set_check를 만든다.

5. set_check 차집합 set을 하면 남은 수들이 1과 5000사이에 있는 self number가 된다.

 

Code:

import java.util.HashSet;
import java.util.Iterator;


public class SelfNumberFinder {
	public static void main(String arg[]) {
		int limit = 5000; // 1에서 5000사이의 self-number를 찾는 프로그램이다.

		HashSet<Integer> set = new HashSet<Integer>();
		HashSet<Integer> set_check = new HashSet<Integer>(limit); // 1부터 5000까지의 수를 저장할 set		
		for(int nat_num = 1; nat_num <= limit; nat_num++) {
			//각 자릿수의 합을 구하는 첫번째 방법: string으로 바꾸고, 
			//str.charAt(int i)을 이용하여 i번째 인덱스의 char ch값을 받아서
			//char값을 Character.getNumericValue(char ch)로 int 형으로 변환
			int temp_int = 0;
			String temp_str = String.valueOf(nat_num); // nat_num을 string으로 변환.
			for(int i = 0; i < temp_str.length(); i++) {
				char ch = temp_str.charAt(i); // i번째 string의 값을 추출해서 ch에 저장
				temp_int += Character.getNumericValue(ch); // ch값을 int로 추출해서 temp_int에 더해서 저장.
			}
			set_check.add(nat_num); // 1부터 5000까지의 값을 hashset에 저장.
			set.add(nat_num + temp_int); // HashSet set에 값 저장.
		}
		set_check.removeAll(set); // 차집합의 결과가 곧 1부터 5000까지의 자연수 중 self number
		Iterator iter = set_check.iterator(); // Iterator iter선언.
		
		while(iter.hasNext()) { 
			System.out.println(iter.next());
		}
	}	
}

위 Idea의 2번 과정이 너무 복잡해서 더욱 간단한 코드로 다시 구현해보았다.

아래는 Idea의 2번 과정만 수정한 코드이다.

import java.util.HashSet;
import java.util.Iterator;


public class SelfNumberFinder {
	public static void main(String arg[]) {
		int limit = 5000; // 1에서 5000사이의 self-number를 찾는 프로그램이다.

		HashSet<Integer> set = new HashSet<Integer>();
		HashSet<Integer> set_check = new HashSet<Integer>(limit); // 1부터 5000까지의 수를 저장할 set		
		
		for(int nat_num = 1; nat_num <= limit; nat_num++) {
	
			int num = nat_num;
			int sum = 0;
			while(num!=0) {
				sum += num%10; //num을 10으로 나눈 값을 더해서 sum에 저장
				num /= 10; //num은 10으로 나눈 몫으로 초기화.
			}

			set_check.add(nat_num); // 1부터 5000까지의 값을 hashset에 저장.
			set.add(nat_num + sum); // HashSet set에 값 저장.
		}
		set_check.removeAll(set); // 차집합의 결과가 곧 1부터 5000까지의 자연수 중 self number
		Iterator iter = set_check.iterator(); // Iterator iter선언.
		
		while(iter.hasNext()) { 
			System.out.println(iter.next());
		}
	}	
}

위의 코드에서 수정된 부분은 다음과 같다.

 

 

			int num = nat_num;
			int sum = 0;
			while(num!=0) {
				sum += num%10; //num을 10으로 나눈 값을 더해서 sum에 저장
				num /= 10; //num은 10으로 나눈 몫으로 초기화.
			}

위의 while문은 쓰임새가 많으니 외워두자.

 

실행결과는 다음과 같이 나온다.