[백준] 4673번 셀프 넘버 -자바(JAVA)

https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

1번 코드

진짜 무식하게 들이댄 방법이다.  각 숫자 하나마다 일일이 셀프넘버인지 아닌지를 판단하는 코드이다.

최악의 경우(=셀프넘버인 경우) 반복문의 횟수가 최대가 되기 때문에 비효율적인 방법이라 할 수 있다.

public class Main {
	public static boolean is_selfnum(int a) {
		
		for(int i = 1; i < a; i++)
		{
			int k = a-i;
			int m = a-i;
			int j = 0;
			while(k > 0) {
				j += k % 10;
				k = k/10;
			}
			if(j != 0 && a == m+j) return false;
		}
		return true;
	}
	
	public static void main(String[] args) {
		for(int i = 1; i <= 10000; i++)
		{
			if(is_selfnum(i) == true) System.out.println(i);
		}
	}
}

 

2번 코드

1번 코드에서는 각 숫자 하나마다 일일이 생성자가 있는지 아닌지 아닌지를 판단하기 때문에, 생성자가 없는 셀프넘버일 경우, for문이 최대로 돌아간다는 단점이 있었다. 이를 개선하기 위해 다른사람들의 코드를 참고해서 2번 코드를 작성했다.

 

2번 코드에서는 1번 코드에서 쓴 방법과는 역방향으로, n을 통해 만들어지는 d(n)은 셀프넘버가 아님을 활용한다.

1부터 10000까지의 숫자들이 셀프넘버인지 아닌지에 관한 정보를 저장하기위해 boolean 배열을 사용하였다.

boolean 배열의 기본값은 false이기 때문에 최대한 기본값을 활용하기 위해, 숫자 i로 만들어진 d(i)는 셀프넘버가 아니므로 notselfnum[d(i)]=true로 바꿔주도록 하였다.

이를 여러번 반복하면 최종적으로 셀프넘버인 수들은 notselfnum의 값이 true로 바뀌지 않고 false 상태로 남아있게 된다.

결과적으로는 notselfnum[n] == false인 수 n들만 출력된다.

public class Main {
	public static int d(int n) {
		
		int sum = n;
		while(n > 0) {
			sum += n % 10;
			n = n/10;
		}
		return sum;
	}
	
	public static void main(String[] args) {
		boolean notselfnum[] = new boolean[10001]; //초기값false
		for(int i = 1; i <= 10000; i++)
		{
			int j = d(i);
			if(j <= 10000) notselfnum[j] = true; // 생성자 i로 생성된 d(i) = j는 셀프넘버가 아니므로 true로 바꿔줌
			
		}
		
		for(int i = 1; i <= 10000; i++)
		{	
			if(notselfnum[i] == false) System.out.println(i);
		}
	}
}

 

시간이 줄었다...!