[백준/알고리즘/python/java] 4673번 - 셀프 넘버

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

[4673번 : 셀프넘버]

이전에 자바로 풀었던 문제를 파이썬을 공부하면서 다시 풀어봤다.

이런 유형의 문제는 일단 숫자를 다 써보면서 이해하는게 빠르다.

문제에서 말하는 셀프 넘버란 생성자가 없는 숫자를 말한다.

(여기서 '생성자'란 어떠한 숫자를 만들 수 있는 숫자를 가리킨다.)

 

쉽게 예를 들어보자면,

1 : 1+1 = 2 를 만들 수 있다. (반면, 1은 어떠한 숫자로도 생성될 수 없다.)-> self_number(o)

2 : 2+2 = 4 를 만들 수 있다. ( 1로 2를 만들 수 있으므로 셀프넘버가 아니다.) -> self_number(x)

3 : 3+3 = 6 을 만들 수 있다. ( 반면, 3은 어떠한 숫자로도 생성될 수 없다.) -> self_number(o)

4 : 4+4 = 8 을 만들 수 있다. ( 2로 4를 만들 수 있으므로 셀프넘버가 아니다.) -> self_number(x)

5 : 5+5 = 10 을 만들 수 있다.  ( 반면, 5는 어떠한 숫자로도 생성될 수 없다.) -> self_number(o)

6 : 6+6 = 12 을 만들 수 있다. ( 3으로 6을 만들 수 있으므로 셀프넘버가 아니다.) -> self_number(x)

7 : 7+7 = 14 을 만들 수 있다.  ( 반면, 7은 어떠한 숫자로도 생성될 수 없다.) -> self_number(o)

8 : 8+8 = 16 을 만들 수 있다. ( 4로 8을 만들 수 있으므로 셀프넘버가 아니다.) -> self_number(x)

9 : 9+9 = 18 을 만들 수 있다.  ( 반면, 9는 어떠한 숫자로도 생성될 수 없다.) -> self_number(o)

10 : 10+1+0 = 11 을 만들 수 있다. ( 5로 10을 만들 수 있으므로 셀프넘버가 아니다.) -> self_number(x)

11 : 11+1+1 = 13 를 만들 수 있다. ( 10으로 11을 만들 수 있으므로 셀프넘버가 아니다.)->self_number(x)

12 : 12+1+2 = 15 을 만들 수 있다. ( 6으로 12를 만들 수 있으므로 셀프넘버가 아니다.) -> self_number(x)

13 : 13+1+3 = 17 을 만들 수 있다. ( 11로 13를 만들 수 있으므로 셀프넘버가 아니다.) -> self_number(x)

14 : 14+1+4 = 19 을 만들 수 있다. ( 7로 14를 만들 수 있으므로 셀프넘버가 아니다.) -> self_number(x)

15 : 15+1+5 = 21 을 만들 수 있다. ( 12로 15를 만들 수 있으므로 셀프넘버가 아니다.) -> self_number(x)

...

...

결국 여기서 어떻게 셀프넘버를 추출할 것이냐가 관건이다.

셀프넘버는 어떠한 숫자로도 합성될 수 없으므로 1부터 1000까지 숫자를 돌면서 해당 숫자를 통해 새로 만들어지는 숫자는 셀프넘버가 아니라는 것을 알 수 있다.

 

셀프넘버에 해당되는 것은 전체 수에서 셀프넘버인 수를 제외하면 되는 것이다.

 

코드는 아래와 같다.

def d(number):
    number_to_string = str(number)
    for idx in range(len(number_to_string)):
        number += int(number_to_string[idx])
    if(number <= 10000):
        check_self_number[number] = True


check_self_number = []
for i in range(10001):
    check_self_number.append(False)

for i in range(1, 10001):
    d(i)
    if(check_self_number[i] == False):
        print(i)

길이가 10000인 check_self_number 라는 리스트를 생성하고, 모든 인덱스를 돌면서 리스트 값을 False 로 초기화한다.

(우선 1부터 10000까지의 수를 모두 셀프넘버라고 가정)

 

d라는 함수를 만들어서 해당 숫자를 문제의 의도에 맞게 합성한다.

로직은 기존 숫자를 string으로 형변환하고 그 숫자와 각 자리에 위치한 숫자를 다 더한 새로운 수를

number 변수에 할당한다. 

number 변수가 10000보다 작거나 같으면 check_self_number라는 리스트의 number 인덱스를 True 로 바꿔준다.

(그 number는 셀프넘버가 아니라는 소리다.)

 

다시 반복문을 통해 해당 인덱스가 가리키는 리스트 check_self_number의 원소값이 False 이면,

그 숫자를 그대로 출력하면 된다. (셀프넘버 출력)

 

(자바 코드)

import java.util.Arrays;
public class Main{
	public static final int MAX = 10001;
	public static int notSelfNumber;
	static int d(int n) {
		int dn= n;
		while(n>0) {
			dn += n % 10;
			n /=10;
		}
		return dn;
	}
	public static void main(String[] args) {
		boolean[] selfAry = new boolean[MAX];
		Arrays.fill(selfAry,true); // Arrays 라이브러리에 있는 fill 메소드 사용
		for(int i=1;i<MAX;i++) {
			notSelfNumber = d(i);
			if(notSelfNumber < MAX) {
				selfAry[notSelfNumber] = false;
			}
		}
		for(int i= 1; i<selfAry.length;i++) {
			if(selfAry[i]) {
				System.out.println(i);
			}
		}
	}
}