문제 정리

---

d(n) = n + n의 각 자리수이고
n은 d(n)의 생성자라고 부를 때

생성자가 없는 숫자를 셀프 넘버라고 부른다
10,000보다 작거나 같은 셀프넘버를 구해야 한다.

입력

없음

출력

10,000보다 작은 모든 셀프넘버를 출력

idea 정리

---

에라토스테네스의 채와 비슷한 느낌으로 하면 된다.

에라토스테네스의 채 설명 글
에라토스테네스의 채는 소수를 걸러내는 알고리즘인데, 2부터 시작해 현재 수의 모든 배수를 걸러내는 방식이다. 걸러지고 남은 수들은 모두 소수이다.

이 문제에서는 1부터 10,000까지 생성자로 다음 순열을 구해 visited 체크 해 주면 된다.

• 수정
  기존 방식은 for문안에서 while문을 돌렸는데 for문 하나로 해결 가능한 방법이 생각나서 개선해봤다.
  아래의 내용은 for문 하나로 해결하는 방식이다.

알고리즘 정리

---

1. 1부터 10,000까지 반복
   1-1. 현재 숫자 i를 생성자로 하는 다음 순열 구해서 방문처리
   1-2. 다음 순열이 10000 초과일 경우는 제외
2. visited가 false인 숫자 모두 출력

구현

---

//셀프 넘버
public class Main {
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		visited = new boolean[10001];
		
		for(int i=1; i<=10000; i++) {
			int start = i;
			start = next(start);
			if(start >= 10000) continue;
			visited[start] = true;
		}
		
		for(int i=1; i<10000; i++) {
			if(visited[i]) continue;
			bw.write(i + "\n");
		}
		bw.flush();
		bw.close();
	}
	
	static int next(int start) {
		int result = start;
		while(start > 0) {
			result += start%10;
			start = start/10;
		}
		return result;
	}
}

결과

---