[JAVA] 백준 4673번 셀프넘버 : 아리토스테네스의 체

 

4673번: 셀프 넘버

 

1. 문제 추상화

 

1 ~ 10000 중 셀프 넘버인 수를 출력하시오.

 

2. 알고리즘 

 

- 아리토스테네스의 체

boolean 배열을 만들어 셀프넘버인 수와 아닌 수를 True와 False로 구분

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

1) 나의 풀이

package boj4673;

public class Main {
	// 에라토스테네스의 체
	// 나의 풀이
	public static void main(String[] args) {
		
		boolean[] decimalArray = new boolean[10050];
		//합이 10000이 넘어가는 제약상황을 자료구조에 투영했다.
		//제약위반이 발생하면 조건문으로 처리하고 자료구조는 문제에 주어진 조건을 그대로 따른다.
		
		for(int i=1; i<=10000;i++) {
			int j = d(i);
			decimalArray[j] = true;
		}
		for(int j=1; j<=10000;j++){
			if(decimalArray[j]==false) {
				System.out.println(j);
			}
		}
	}
	
	public static int d(int data) {
		int result = data;
		
		while(data > 0) {
			int value = data%10;
			data /= 10;
			result += value;
		}
		return result;
	}
}

 

2) 일반적인 풀이

public class Main {
		// 다른 사람 풀이
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 자료구조는 제약이 적용된 상태가 아닌 조건으로 주어진 그대로로 만든다.
		// 제약은 조건 및 반복으로 구현한다.
		int size = 10001;
		boolean[] isNotSelfNumber = new boolean[size];
		
		for(int i=1; i<isNotSelfNumber.length;i++) {
			int result = d(i);
			if(result < size) {
				isNotSelfNumber[result]= true;
			}
		}
		
		for(int i=1; i < isNotSelfNumber.length; i++) {
			if(isNotSelfNumber[i]==false) {
				System.out.println(i);
			}
		}
	}
	
	public static int d(int data) {
		int result = data;
		while(data > 0) {
			result += data%10;
			data /= 10;
		}
		return result;
	}

}

 

 

개선해야 될 점

 

배열이나 리스트는 조건에 주어진대로 만든다. 

제약조건은 if나 for문으로 구현한다. 

자료구조에 제약조건을 반영하지 말자.