알고리즘 풀이/백준

[백준][Java] 4673번 셀프 넘버

배게 2018. 4. 17. 19:17
728x90

무한수열 알고리즘은 짰는데 셀프넘버만 추리는 방법을 어떻게 해야될지

고민했습니다.

1부터 만까지 counting하면서 셀프숫자가 아닌 숫자들을 피해서 돌렸습니다.


unSelNo -> 생성자로 만든 셀프숫자가 아닌 수들의 배열

selNo -> 생성자가 없는 셀프 숫자 ( unSelNo에 속하지 않은 값들 )


unSelNo에 속하지 않는 counting된 값들을 selNo에 넣어주면서 새로운 unSelNo에 속할

값들을 for문을 사용하여 갱신해줍니다.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		int gNum,pos,uNum,rNum,oToH;
		ArrayList<Integer> unSelNo= new ArrayList<Integer>();
		ArrayList<Integer> selNo= new ArrayList<Integer>();
		//gNum : 현재 진행중인 값, pos : 자리수
		//uNum : 자리별 숫자, rNum : 앞자릿수부터 순서대로 제거하고 남은 숫자
		oToH=1;
		int Max=10000;
		
		while(oToH<Max) {
			while(true) {
				if(!unSelNo.contains(oToH)) {
				
					if(oToH<Max) selNo.add(oToH);
					gNum=oToH++;
					break;
				}
				else oToH++;
			}

			while (gNum < Max) {
				pos =(int)(Math.log10(gNum));
				rNum = gNum;
				// System.out.println(gNum);
				for (int i = pos; i >= 0; i--) {
					uNum = (int) (rNum / Math.pow(10, i));
					rNum -= (int) (uNum * Math.pow(10, i));
					gNum += uNum;
				}
				if(gNum>=Max) break;
				if(!unSelNo.contains(gNum) ) unSelNo.add(gNum);
//				System.out.println(gNum);
			}
		}
		for (Integer integer : selNo) {
			System.out.println(integer);
		}
	}
}