알고리즘 (6월 6일)

1. 문제 (코딩도장, 넥슨 입사문제)

https://codingdojang.com/scode/365?answer_mode=hide 

코딩도장

---

2. 생각

어떤 자연수 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 보다 작은 모든 셀프 넘버들의 합을 구하라.

 

 

1. 자연수 n을 입력받는다.
2. 1 ~ n 까지 숫자들을 Generator 라고 생각하고, ArrayList에 저장한다.
3. for문을 통해 1부터 n까지 해당 숫자가 Generator인지 확인한다.
4. Generator가 아니면 ArrayList에서 삭제하고, Generator가 맞으면 유지한다.
5. 남은 ArrayList의 원소들은 Generator이기 때문에 for문을 통해 1 ~ n까지의 Generator의 합을 구한다.

---

3. 풀이 및 코드 분석

import java.util.Scanner;
import java.util.ArrayList;


public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		ArrayList<Integer> generator = new ArrayList<>();
		
		int n;
		
		// 자연수 n 입력 받기
		while(true) {
			System.out.println("자연수 n을 입력하시오:");
			n = scan.nextInt();
			
			if(n<1) {
				System.out.println("잘못 입력하셨습니다.\n");
			}else {
				break;
			}
		}
		
		// 1부터 n까지 숫자들을 Generator라고 초기 설정 
		for(int i=1; i<n; i++) {
			generator.add(i);
		}
		
		// Generator가 아니면 generator 리스트에서 삭제
		for(int i=1; i<n; i++) {
			ArrayList<Integer> digits = new ArrayList<>();
			int j = i;
			int isGenerator=i;
			
			while(j>0) {
				digits.add(j%10);
				j /= 10;
			}
			
			// isGenerator = 본인 + 각 자릿수
			for(int k=0; k<digits.size(); k++) {
				isGenerator += digits.get(k);
			}
			
			// generator 리스트에서 generator가 아닌 수를 삭제
			if(isGenerator < n) {
				Object x = (Integer)isGenerator;
				generator.remove(x);
			}
		}
		
		// sum of generator
		int sumOfGenerator=0;
		
		for(int i=0; i<generator.size(); i++) {
			int j = generator.get(i);	
			sumOfGenerator += j;	
		}
		
		System.out.printf("Sum of Generator : %d\n", sumOfGenerator);
	}
}