[백준알고리즘-JAVA]4673번 풀이(셀프넘버)

안녕하세요

인포돈 입니다.

백준 알고리즘 4673번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 4673 (셀프 넘버)

 

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자릿수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

 

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))),... 과 같은 무한수열을 만들 수 있다.

 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런 식으로 다음과 같은 수열을 만들 수 있다.

 

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141,...

 

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다.

 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

 

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

입력

입력은 없다.

 

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

 

입력 예시

x

 

출력 예시

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

 

성공코드

public class Main {
	public static void main(String args[]){
					
		boolean[] checkbox = new boolean[10001];
		
		for(int i=1;i<10001;i++) {
			int tmp = selfnumber(i);
			if(tmp <= 10000)
				checkbox[tmp] = true;
		}
		StringBuilder sb = new StringBuilder();
		for(int i=1;i<10001;i++) {
			if(!checkbox[i])
				sb.append(i).append('\n');
		}
		System.out.print(sb);

	}
	public static int selfnumber(int num) {
		int sum = num;
		while(num != 0){
			sum = sum + (num % 10);
			num = num/10;
		}
   
		return sum;
	}
	}

 

사실 이번 문제를 풀어볼 때 많이 헤매었었습니다. 배열을 사용해야 되는 것을 인지하고 있었지만 String, Integer로 배열을 생성하면, 어떤 식으로 셀프 넘버를 판별할지 감이 잡히지 않았다. 결론적으로는 다른 분들의 힌트를 듣고 해답을 찾아나갔습니다.

 

해당 문제에서 중요한 문제는 2가지라고 생각합니다. 배열을 이용하여 어떻게 셀프넘버를 표현할 것인가?, 어떤 형식으로 셀프넘버를 뽑아낼 것인가? 

 

첫 번째 의문을 해결하기 위해서는 String, Integer 외에도 Boolean, Object 등 다른 타입의 배열을 생성할 수 있다는 것을 항상 염두에 두어야 한다.

 

두 번째 의문을 해결하기 위해서는 약간의 사고력이 필요하다고 생각한다. 대부분의 수학이 들어가는 문제들에서 우리가 대체로 한 번에 해결책이 보이지 않는 경우에는 '%'라는 나머지를 구하는 연산자가 들어가 있는 경우가 많다는 것을 알 수 있습니다.

 

우리는 대게 %를 사용하지 않기 때문이죠. 이를 이용해 셀프 넘버를 쉽게 파악할 수 있습니다.

 

	public static int selfnumber(int num) {
		int sum = num;
		while(num != 0){
			sum = sum + (num % 10);
			num = num/10;
		}
   
		return sum;
	}

 

입력받은 인자를 sum변수에 넣어준 뒤 sum + (num %10);을 해줍니다. 이러한 연산을 하는 이유는 바로 가장 작은 자릿수에 있는 값을 더해주는 것이죠.

 

num = num/10의 경우에는 더한 가장 작은 자리 수를 제거하는 역할을 하죠. 

 

역시나 말보다는 숫자가 빠르겠네요.  만약 103이라는 숫자가 들어왔다고 가정해보죠

 

sum = 103

1 번째

sum = 103 + (103%10) = 106

num = 103/10 = 10

2번째

 sum = 106 + 10%10 = 106

num = 10/10 = 1

3번째

sum = 106 + (1%10)=107

num = 1/10 = 0

 

while문이 나오게 됩니다. 그러면 sum에는 107의 값이 나오게 됩니다.

 

 

그렇다면, 이렇게 나온 수를 Boolean배열에 True라는 값으로 넣어줍니다. (왜 false가 아니라 true 넣어주냐??

바로 Boolean은 default값(기본값)으로 false를 가지고 있기 때문에 만약 selfnumber라면 false의 값을 가지고 있게 만들어 주기 위해서 이죠)

 

보다 쉬운 방법이어서 그렇습니다. 

 

앞서 본 예시처럼 103을 넣었더니 107이 나오게 되었어요. 그러면 이제 107번 인덱스에 true의 값을 넣어주는 거죠 생성자가 있으니 셀프 넘버가 될 수 없는 수이기 때문이죠.

 

이와 같이 계속 반복을 한다면 원하는 결과 값이 나오게 됩니다.

 

해당 문제는 꽤나 생각이 필요했던 문제라고 생각합니다. 꼭 기억해야 될 점은 boolean의 활용성, % 의 활용 이 두 가지를 이번 알고리즘에서 잊지 않았으면 합니다.