[백준|파이썬] 4673: 셀프 넘버 (실버5)

문제

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

4673번: 셀프 넘버

 

 

❓ 셀프 넘버

생성자가 존재하는 숫자는 아래와 같다. 

👇

1+1 = 2

2+2 = 4
3+3 = 6
4+4 = 8
5+5 = 10
6+6 = 12
7+7 = 14
8+8 = 16
9+9 = 18
10+1+0 = 11
11+1+1 = 13
12+1+2 = 15
13+1+3 = 17
14+1+4 = 19
15+1+5 = 21
16+1+6 = 23
17+1+7 = 25
18+1+8 = 27
19+1+9 = 29
20+2+0 = 22
...(중략)
50+5+0 = 55
...(중략)
100+1+0+0 = 101

...(중략)

999+9+9+9 = 1026

 

따라서 위 목록에 해당되지 않는 번호가 셀프 넘버(1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97,...)이다.

처음에 셀프 넘버를 이해하지 못해서 아래 블로그의 설명을 참고했다.

https://d-life93.tistory.com/396

 

 

🐍파이썬

temp = [i for i in range(1, 10000)]
arr = set()
for i in temp:
    num = i
    for j in str(i):
        num += int(j)
    arr.add(num)
for i in sorted(set(temp)-arr):
    print(i)

1️⃣ 1 ~ 999까지의 정수를 담은 temp배열을 순회하면서 숫자 num + 각 자리 수의 조합으로 숫자를 생성한다. 이때 만들어진 수는 num을 생성자로 하는 수이므로 셀프 넘버가 아니다.

2️⃣ 만들어진 수는 리스트에 담아 set으로 형변환한 temp에서 빼 차집합 연산을 한다. 차집합 연산으로 temp에 존재하는 arr의 원소를 모두 제거할 수 있다. 이때, set은 원소의 순서를 무시하는 자료구조이므로 sorted를 이용해 오름차순 연산을 해주는 것이 중요하다.(처음에 이걸 안 해줘서 여러 번 실패 떴음...)

 

---

각 자리수 덧셈을 문자열 처리하지 않고 divmod로 처리한 코드

temp = [i for i in range(1, 10000)]
arr = set()
for i in temp:
    num = i
    num2 = i
    while num2 > 0:
        num2, n = divmod(num2, 10)
        num += n
    arr.add(num)
for i in sorted(set(temp)-arr):
    print(i)

각 자리수 덧셈 이외의 로직은 위의 코드와 동일하다.

 

 

다른 풀이 방법

n_list = [0 for _ in range(10001)]

def d(n):
    s = n
    while n > 0:
        s += (n % 10)
        n //= 10
    return int(s)

for i in range(1, 10001):
    check = d(i)
    if check < 10001:
        n_list[check] = 1
    
for i in range(1, 10001):
    if n_list[i] != 1:
        print(i)

n_list = [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...(중략)..., 1, 1, 1, 1]

1️⃣ 인덱스 0 ~ 10000까지의 리스트 n_list를 생성하고 1~10000까지 루프를 돌며 셀프 넘버가 아닌 수를 체크한다.

2️⃣ 해당 수를 인덱스로 하여 n_list의 원소값을 1로 바꾼 뒤 또 다른 for문을 통해 n_list에서 원소의 값이 0인 수(셀프 넘버)의 인덱스를 출력해 주었다.