[백준]4673. 셀프 넘버 (파이썬, python)

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

4673번: 셀프 넘버

1. 문제 분석

 이번 문제를 분석해보자면

1. 기존 수를 n이라고 하면, 다음 수 d(n)을 구하는 공식은 n과 n의 각 자리수를 더하는 것이다.

ex) d(35) = 35 + 3 + 5 = 43

2. 이때, 35는 43의 생성자라고 한다.

3. 이런 생성자가 없는 숫자를 셀프 넘버라고 하고, 10000보다 작거나 같은 셀프 넘버들을 출력해라.

 

2. 문제 해결 방향

 결국 문제에서는 셀프 넘버가 아닌 수를 구하는 방법을 알려주었다. 곰곰히 생각해본 결과, 셀프 넘버인지 확인하는 알고리즘을 따로 생각하는 것 보다,

 

1. 셀프넘버가 아닌 수를 확인하는 방법을 통해 셀프 넘버가 아닌 수들을 저장하고,

2. 다른 공간에 1~10000까지의 수에서 저장한 수들을 제외한 값을 저장하여

3. 그 수들을 출력하는 방법을 택하였다.

 

3. 코드

(설명은 주석 참고)

# 10000보다 작거나 같은 셀프 넘버들을 출력

# 둘다 set를 사용함으로서
# 중복제거, 뺄셈 연산 가능하게 함
nums = set(range(1, 10001))
not_self = set()

# 셀프 넘버가 아닌 수들 not_self에 저장
for i in range(1, 10001):
    tmp = i # 규칙에 의한 다음수
    for j in str(i):
        tmp += int(j)
    not_self.add(tmp)

# 셀프 넘버들 찾기
result = nums - not_self
result = list(result)
result.sort()

# 결과 print
for i in result:
    print(i)

 

문제 코드는 github에 올려두었다.

https://github.com/imgzon3/algorithm/blob/main/1_%EB%B0%B1%EC%A4%80/2_%EB%AC%B8%EC%A0%9C_1/4673.py

GitHub - imgzon3/algorithm: 코딩 테스트 연습