[백준 알고리즘] 4673번 셀프 넘버

[4673] 셀프 넘버

 

 

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다.

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

 

 

 

출력

입력 값은 없고, 아래 예제처럼 출력되어야 합니다.

 

 

 

 

🔧접근 방법

 

1.  1~10000 까지의 set 생성

 

2. 생성자를 가지는 숫자들을 찾아 해당하는 값을 set에서 버림

 

3. 버리고 남은 숫자들 출력

 

 

 

 

💻 코드 

# 1~ 10000까지의 숫자를 가진 set 생성
result = set([i for i in range(1,10001)])


for i in range(1,10000):
    sum = i # 본래의 숫자
    for j in range(len(str(i))): # 각 자리 수 더함
        sum += int(str(i)[j])
    result.discard(sum)   # sum 값에 해당되는 숫자 버리기

# 셀프 넘버만 남은 숫자 출력
for i in result:
    print(i)
    

 

 

🎈 list가 아닌 set을 사용한 이유

 

- 처음에는 자주 쓰이는 리스트로 하려 했으나, 101같은 경우는 생성자가 2개가 있어 중복되는 경우가 발생합니다. list는 이미 지워진 값을 remove 하면 에러가 발생하는데, set 같은경우는 remove 대신 discard가 있어 값이 없더라도 에러가 발생하지 않기 때문이다.

 

 

 

 

 

⏳ 개선한 코드

 

for 문 안에 for 문을 넣어서 돌리자니 비효율적인 부분이 있었습니다. 그래서 for문을 없애고자, sum과 map을 활용해 다시 코드를 짜봤습니다.

 

 

# 1~ 10000까지의 숫자를 가진 set 생성
self_number = set([i for i in range(1,10001)])
minus = set()

for i in range(1, 10001):
    minus.add(sum(list(map(int, str(i))))+i)

self_number = sorted(self_number - minus)
for i in self_number:
    print(i)

 

 

 

그랬더니 메모리는 조금 늘어났지만, 시간은 12ms 단축 되었습니다.. 

 

 

 

 

 

 

 

# 바보같은 실수 하나 했는데요..

sum을 변수로 두어서 'int' object is not callable 이라는 에러가 떴습니다....

저처럼 실수 하지 마시길... 변수 이름 잘 지읍시다!