[Java] Self-number 알고리즘과 합

 

Self-number(셀프 넘버) 알고리즘 문제

 

 

 

package selfnumberQuiz;

public class SelfNumberQuiz {

	public static void main(String[] args) {
		
		/*
		 * 어떤 자연수 n이 있을때, d(n)을 n의 각 자릿수 숫자들과 n자신을 더한숫자라고 정의
		 * 예를 들어 d(91) = 9+1+91=101과 같은식이 있을때 
		 * n을 d(n)의 제너레이터라고 함.
		 * 위의 예에서 91은 101의 제너레이터 이다.
		 * 어떤 숫자들은 다음과 같이 하나 이상의 제너레이터를 갖고있다.
		 * 101의 제너레이터는 91뿐 아니라 100( d(100) = 1+0+0+100=101)도 있다.
		 * 어떤숫자들은 제너레이터를 가지고 있지 않다.
		 * 이런 숫자를 인도 수학자가 셀프넘버라고 이름붙였다.
		 * 예를들어 1,3,5,7,9,20,31,....은 셀프넘버이다.
		 * 
		 * 문제 > 1이상이고 5000보다 작은 모든 셀프넘버들의 합을 구하라.
		 * 
		 * */
		
		int[] dn = new int[5000];	//제너레이터를 갖는수를 담을 배열
		int[] digit = new int[5000];	//1~5000을 갖을 배열
		int sum = 0;
		for(int i = 0; i < 5000; i++) {
			digit[i] = i+1;
		}
		
		for(int i = 0; i < 5000; i++) {
			dn[i] = digit[i] + digit[i]%10 + (digit[i]%100)/10 + 
            	(digit[i]%1000)/100 + digit[i]/1000;
			//System.out.println(dn[i]); // 제너레이터를 갖는 수
		}
	
		for(int i = 0; i < 5000; i++) {
			for(int j = 0; j < 5000; j++) {	
				if(digit[i] == dn[j]) {
					digit[i] = 0;	
                    //제너레이터를 갖는수와 같은값이라면 0으로 만든다=>셀프넘버만 0이아니게됨
				}
			}
			//System.out.println(digit[i]);	
			sum+=digit[i];	//셀프넘버외에는 전부 0이므로 합하면 셀프넘버의 합이나옴
		}
		System.out.println(sum);

	}

}

 

답

 

 

다행이 답은 잘 나오는데, 효율적으로 동작하지는 않는 느낌이다.

불필요한 데이터가 많은 것 같다.

더 좋은 아이디어가 있는지 찾아서 내 코드랑 비교해봐야겠다.

 

끝!