[python] 백준 4673 : 셀프 넘버

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

4673번: 셀프 넘버

난이도 : 실버5

분류 : 수학, 구현, 브루트포스

---

1 : 문자열을 이용한 풀이

lst = list(range(1, 10001))
wow = []
for i in range(len(lst)):
    for j in str(i):
        i += int(j)
    wow.append(i)
wow.sort()
for i in lst:
    if i not in wow:
        print(i)

먼저 1~10000까지의 자연수를 lst에 담는다.

반복문으로 해당 자연수와 그 수의 자릿수끼리 전부 더한 값을 합하고 wow라는 리스트에 추가한다.

이 값은 해당 자연수의 분해합과 같다.

i가 103이라면 wow에 103+1+0+3 = 107이 들어가는 것이다.

 

sort()함수로 wow에 들어있는 값을 오름차순으로 정리한다.

lst의 1~10000까지의 자연수 중에서 wow에 들어가 있는 값을 제외시키면 1~10000까지의 셀프 넘버를 추출할 수 있다.

 

 

2 : 리스트를 이용한 풀이

lst = list(range(1, 10001))
wow = []
for i in range(len(lst)):
    nlst = list(map(int, str(lst[i])))
    wow.append(lst[i] + sum(nlst))
wow.sort()
for i in lst:
    if i not in wow:
        print(i)

위와 같은 코드이지만 각 자리수를 나누는 방법에서 차이가 있다. 속도는 둘다 비슷하다.

 

---

 

3 : (다른 사람 풀이) set() 자료형을 이용한 풀이

 

set() 자료형은 집합 자료형이다. 따라서 A-B(차집합)과 같은 연산을 할 수 있다.

for i in lst:
    if i not in wow:
        print(i)

이 방법은 반복문과 조건문이 같이 있다보니 시간이 오래걸렸다. 차집합을 이용해 필요한 값만 골라내면 훨씬 더 빨리 처리할 수 있었다.(리스트에서는 차집합을 할 수 없다.)

 

num = set(range(1,10001))
rmv = set()
for i in range (1,10001):
    for j in str(i):
        i += int(j)
    rmv.add(i)
num = num - rmv
for k in sorted(num):
    print(k)

num은 1~10000까지 자연수에 대한 집합이,

rmv은 분해합들의 집합이 담겨진다.

 

셀프 넘버는 num - rmv (차집합)과 같으므로 num = num - rmv로 값을 추려내고,

sorted()함수를 이용해 오름차순으로 셀프 넘버를 하나씩 출력한다. (set()을 쓰면 순서가 뒤죽박죽이 되어 정렬을 해주어야 한다.)