[Python/파이썬] 백준 알고리즘 4673번 - 셀프 넘버

생성자가 없는 숫자가 '셀프 넘버' 이고 이 셀프 넘버들을 쭉 나열하는 프로그램을 짜보라는 문제이다.

 

 

 

<풀이>

# 함수 d(n)
def d(n):
    # 생성자 n을 이용해 d(n)을 만드는 수식
    n = n + sum( map(int, str(n)) )
    return n

# 셀프 넘버가 아닌 수들(생성자가 있는 수들)이 들어갈 집합
nonSelfNum = set()

# nonSelfNum 집합에 들어갈 수들을 찾아 넣기
for i in range(1, 10001):
    nonSelfNum.add( d(i) )

# 셀프 넘버들을 출력하기
for j in range(1, 10001):
    if j not in nonSelfNum:
        print(j)

먼저 프로그램의 구조는 다음과 같다.

1. 셀프 넘버가 아닌 수들(생성자가 있는 수들)을 모두 구해 집합에 넣는다.

2. for문을 1부터 10000까지 돌리며 '셀프 넘버가 아닌 수들' 집합에 포함되지 않으면 해당 수를 출력한다.

   ('셀프 넘버가 아닌 수들' 집합에 포함되지 않는다는 것은 셀프 넘버라는 이야기이므로)

 

이제 코드를 보겠다.

우선 생성자 n으로 d(n)을 만드는 수식을 보면 n + sum(map(int, str(n)))으로 되어있다.

int로 들어온 n을 str으로 형변환을 시켜주면 문자열 즉, iterable이 되고 그걸 map 함수를 이용해 다시 int로 바꾸면 sum()함수를 이용해 각 자리 수의 합을 구할 수 있다.

sum() 함수가 받는 인자는 iterable이고 map()은 iterator을 반환하므로 sum() 함수 안에 map()을 바로 써도 괜찮다.

이렇게 함수 d(n)을 구현할 수 있다.

 

다음으로 '셀프 넘버가 아닌 수들' 집합이다. 이 집합은 리스트가 아니라 집합(set)으로 만들었는데 리스트로 해도 상관은 없다. 다만 값들의 중복이 생기는 것이 싫어서 set으로 했다.

 

그리고 for문으로 1부터 10000까지 돌리며 '셀프 넘버가 아닌 수들'을 찾는다.

마지막으로 for문을 1부터 10000까지 다시 돌리며 '셀프 넘버가 아닌 수들' 집합에 포함되지 않는 수들을 출력한다.

 

 

 

<핵심 정리>

1. sum( map(int, str(n)) )을 이용해 정수 n의 각 자리 수들의 합을 구할 수 있다.

2. input의 범위가 정해져 있다면 for문으로 처음부터 끝까지 돌려보는게 해결책일수도 있다.

3. 구해야 하는 집합 A가 있다면 A의 여집합을 모두 구한다음 여집합에 포함되지 않는 요소들을 찾는 방식으로 집합 A를 구할 수도 있다. (여사건 공략)