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

 

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

4673번: 셀프 넘버

 

 

 

---

• 문제

 

 

※ 주의할 점

1. 한 줄에 하나씩 출력해야한다. 그렇다고 a lot more numbers 문자를 출력하는 것은 절대 아니다.
2. 양의 정수. 즉 0보다 크고 10000 보다 작거나 같은 수 중에 셀프 넘버(self number) 을 출력하면 된다.

 

 

---

• 알고리즘

 

먼저 설명하기에 앞서 함수를 굳이 쓰지 않아도 된다. 그러나 함수 카테고리인 만큼 함수를 이용하여 풀어보고자 한다. 그러니 만약 코드를 보고 함수를 쓰고싶지 않다면 쓰지 않고 해도 백준에서는 출력값만 맞으면 성공으로 되니 독자들의 판단하에 선택하면 된다.

 

 

그럼 먼저 셀프 넘버 알고리즘을 구현해보자.

구현 방식은 1 부터 10000까지 검사한 뒤, 해당 수를 생성자로 하는 수가 있으면 그 수를 거르는 것이다.

 

 

먼저 함수는 아래와같이 짠다.

public static void main(String[] args){	// 메인
	for (int i = 1; i < 10001; i++){
		int n = d(i);
	}
}

public static int d(int number) {	// 함수

}

 

1 부터 10000까지 검사할 때  메인에서 d 함수로 숫자를 넣어보며 return 되는 수는 해당 number를 생성자로 하는 수로 구성 할 것이다.

 

 

그럼 d 함수를 좀 더 구체적으로 작성해보자.

 

 

1. 먼저 number 라는 수를 받게되면 number 을 생성자로 하는 수를 리턴시킬 것이기 때문에 sum 이란 변수를 하나 생성한다.

그리고 초기 값은 number 로 한다. (이후 과정에서 왜 number 로 초기화 하는지 알려줄 것이다.)

public static int d(int number){
	int sum = number;
}

 

2. 셀프넘버를 찾기 위한 반복문을 작성해준다.

public static int d(int number){
	int sum = number;
    
	while(number != 0){
    
	}
}

 

일단 각 자리수를 더해주기 위해서 나머지 연산자와 나눗셈 연산자로 10 단위씩 number 을 줄여 갈 것이기 때문에 number 가 0 이 아닐 때 까지 계속 반복해준다.

3. number 의 첫 번째 자리수를 구하기 위해 % 연산자를 사용하여 sum 에 더해주고, 이후 / 로 10을 줄인다.

public static int d(int number){
	int sum = number;
    
	while(number != 0){
		sum = sum + (number % 10); // 첫 째 자리수
		number = number/10;	// 10을 나누어 첫 째 자리를 없앤다
	}
    
	return sum;
}

즉, 위 알고리즘 대로 한다면 아래와 같다.

 

1234 라는 수가 들어왔다고 가정하자. (number = 1234)

그럼 1234 라는 수를 생성자로 하는 수는 다음과 같다.

 

1234 + 1 + 2 + 3 + 4 = 1244

 

즉 sum 에 먼저 1234 라는 수를 선언과 함께 초기화 시켜주었고, 다음 반복문부터 각 자리수를 더해주는 방식인 것이다.

[반복문]

첫 번째 반복 )

number % 10 = 4 이므로 sum 에 4 가 더해져 sum 은 1238 이 된다.

number / 10 = 123 이고 이 수가 새로운 number 가 된다. 즉 number = 123 이 된다.

 

두 번째 반복 )

number % 10 = 3 이므로  sum 에 3 이 더해져 sum 은 1241 이 된다.

number / 10 = 12 이고 이 수가 새로운 number 가 된다. 즉 number = 12 가 된다.

 

세 번째 반복 )

number % 10 = 2 이므로  sum 에 2 가 더해져 sum 은 1243 이 된다.

number / 10 = 1 이고 이 수가 새로운 number 가 된다. 즉 number = 1 이 된다.

 

네 번째 반복 )

number % 10 = 1 이므로  sum 에 1 이 더해져 sum 은 1244 가 된다.

number / 10 = 0 이고 이 수가 새로운 number 가 된다. 즉 number = 0 이 된다.

 

이후 while 조건문에 의해 number 가 0 이므로 반복문을 탈출한다.

그리고 sum 을 return 해주면 된다.

 

4. return 된 수는 생성자가 있는 수, 즉 출력하면 안되는 수 이므로 boolean 배열을 통해 true 로 바꾸어 준다.

public static void main(String[] args){	// 메인

	boolean[] check = new boolean[10001];	// 1부터 10000이므로

	for (int i = 1; i < 10001; i++){
		int n = d(i);
		
		if(n < 10001){	// 10000 이 넘는 수는 필요가 없음
			check[n] = true;
		}
	}
}

public static int d(int number){
	int sum = number;
    
	while(number != 0){
		sum = sum + (number % 10); // 첫 째 자리수
		number = number/10;	// 10을 나누어 첫 째 자리를 없앤다
	}
    
	return sum;
}

즉, 메인에서 보면 d 함수에 의해 리턴된 수 n 을 boolean 배열의 인덱스로 사용하여 해당 위치를 true 로 바꾸어 주는 것이다.

이때 문제에서 나와있듯이 1 부터 10000까지이므로 10001 이상의 수는 필요 없다.

 

 

 

위 과정이 끝나면 마지막으로는 boolean 배열에서 false 인 원소의 위치(인덱스)를 출력해주면 된다.

 

저렇게 쪼개서 설명하면 이해하기 힘들 수 있으니 아래 코드를 보자.

 

---

• 풀이

 

public class Main {

	public static void main(String[] args) {

		boolean[] check = new boolean[10001];	// 1부터 10000이므로

		for (int i = 1; i < 10001; i++){
			int n = d(i);
		
			if(n < 10001){	// 10000 이 넘는 수는 필요가 없음
				check[n] = true;
			}
		}

		StringBuilder sb = new StringBuilder();
        
		for (int i = 1; i < 10001; i++) {
			if (!check[i]) {	// false 인 인덱스만 출력
				sb.append(i).append('\n');
			}
		}
		System.out.println(sb);
	}



	public static int d(int number){
		int sum = number;
    
		while(number != 0){
			sum = sum + (number % 10); // 첫 째 자리수
			number = number/10;	// 10을 나누어 첫 째 자리를 없앤다
		}
    
		return sum;
	}
}    

 

위 코드가 완성코드다.

 

출력할 때 StringBuilder 을 사용해도 되고 아니면 매 순간마다 sb.append 가 아닌 System.out.println() 으로 출력해주어도 된다.

 

 

---

• 성능

 

 

---

• 정리

많이 어려운 문제는 아니였다.

그리고 필자의 코드가 "정답"은 아니다. 알고리즘이야 사람마다 모두 다르게 구성하고 생각 또한 다르기 때문에 어떤 것이 옳다고 단정 할 수는 없다.

 

다만, 독자분들이 조금이라도 이해하기 쉬우면서 성능이 좋은 알고리즘을 알려주려고 노력하고 있기에 많은 분들이 이해가 되었으면 좋겠다.