[ 백준 문제 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

아아!! 어려워하지말자..

 

양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의한대요.

 

매개변수로 n을 가지는 함수 d를 정의해보겠습니다.

 

def d(n):

 

함수 안에 코드를 어떻게 써줄지 고민해봅니다.

리턴하는 건 n과 n의 각 자리수를 더한 값이겠죠!

 

def d(n):
   n = n + sum(map(int, str(n)))
   return n

=> 정수 n을 스트링 타입으로 변환해서 map 함수를 이용해 문자열 각각의 요소를 int형으로 변환해줍니다.

그리고, sum()으로 각 요소들을 더해줍니다.

 

map()

map()는 문자열, 리스트, 튜플과 같은 시퀀스 자료형에 사용할 수 있는 함수입니다.

입력 값을 여러개 받아올 때 써줬던 함수인데요.
map(int, input().split()) 이런식으로 써서 여러개의 입력값을 받아줄 수 있었습니다.

input을 해오면 기본적으로 문자열 타입으로 받아옵니다.
문자열의 요소를 각각 int 형으로 변환해주는 기능을 해주는 게 map 함수였습니다.

입력값을 받아오는 상황이 아니더라도,
시퀀스 자료형의 각 요소에 어떤 작업을 해주고 싶을 때 유용한 함수입니다.

 

자 함수 d를 정의해줬습니다.

이제 셀프넘버 이야기로 넘어갑시다!

 

셀프넘버는 일단 범위가 주어집니다.

1이상 10000이하의 숫자여야합니다.

 

self_num 이라는 리스트를 만들어주겠습니다.

self_num = list(range(1, 10001))

 

이 리스트에서 셀프넘버가 아닌 요소들을 제거해줄 겁니다.

리스트 원소 삭제 세가지
del, .remove(), .pop()

1. del 명령어
del list_name[index]
리스트의 인덱스를 받아서 삭제합니다.

2. .remove()
list_name.remove(element)
인덱스가 아닌 삭제하려는 값을 받아서 삭제합니다.

3. .pop()
list_name.pop(index)
인덱스를 받아서 그 자리에 있는 원소를 꺼내줍니다.

 

이 중 인덱스는 사용안해서

remove() 사용하겠습니다.

 

for j in self_num:
   for k in self_num:
      if d(k) == j:
         self_num.remove(j)

print(self_num)

이렇게 코드를 작성해 줬는데요..

 

j가 리스트에 없어서 제거가 안된다고 뜹니다.

 

생각해보면 생성자가 여러개가 되는 경우도 있다고 했죠?

 

101의 생성자는 91과 100 두 개 라고요.

 

d(91)==101

d(100)==101

 

이러면 j값을 리스트 안에서 두 번 제거해주겠죠?

이미 한 번 없앤 걸 또 없애려고 하니까, 리스트 안에 없다고 하는 겁니다.

 

아하....!

 

셀프넘버가 아닌 수들은 중복이 됩니다.

set()
집합의 특징

- { } 중괄호 또는 set()을 이용합니다.
- 값이 중복되지 않습니다. 고유한 unique한! 값을 가집니다.
- 정해진 순서가 없습니다. 인덱싱 불가능! 슬라이싱 불가능!
- 인덱싱이나 슬라이싱을 해주고 싶다면 list 자료형으로 변환해주면 됩니다.

 

not_self_num 리스트를 만들어

셀프 넘버가 아닌 정수를 넣어주고, 리스트의 요소들이 중복되지 않도록 set 자료형으로 변환해준 뒤

remove()를 해줄게요

 

def d(n):
   n = n + sum(map(int, str(n)))
   return n

self_num = list(range(1, 10001))
not_self_num = []

for j in self_num:
   for k in self_num:
      if d(k) == j:
         not_self_num.append(j)

for l in set(not_self_num):
   self_num.remove(l)

for m in self_num:
   print(m)

이렇게! 소중한 코드를 완성했어요.

에러가 뜨는 것도 아닌데 출력이 안되길래

왜이러나..? 했는데 한~참 있다가 출력됩니다.

 

아니나 다를까 시간초과입니다..ㅋ

 

for j in self_num:
   for k in self_num:
      if d(k) == j:
         not_self_num.append(j)

아마도 제가 이중 for문을 썼는데 1,10001 범위의 리스트를 두번씩 불러오게되면서

시간초과가 나게된 것 같아요.

 

안되면? 고쳐주면 되죠!!!!

 

for j in self_num:
   not_self_num.append(d(j))

이렇게 줄이면 안됩니다.

 

이러면 j의 범위가 1~10000이 되는 건데

j가 10000이라면 d(j)는 는 10001으로 범위를 초과하니까,

나중에 self_num 리스트에서 remove할 때 에러가 날 수 있어요.

self_num리스트엔 10001이없다 뭐 이런식으로 말이죠..

 

---

정답 1: remove() 이용

def d(n):
   n = n + sum(map(int, str(n)))
   return n

self_num = list(range(1, 10001))
not_self_num = []

for i in self_num:
   not_self_num.append(d(i))

for j in set(not_self_num):
   if j <= 10000:
      self_num.remove(j)

for k in self_num:
   print(k)

 

이렇게 고쳐줬습니다!

 

if j < = 10000이라는 조건을 통해 remove 썼을때

에러가 발생하지 않도록 방지했습니다.

 

 

 

▶ set 사용없이 list만 이용해서

문제를 풀 수 있습니다. 

정답 2: if not in 이용

def d(n):
   n = n + sum(map(int, str(n)))
   return n

self_num = list(range(1, 10001))
not_self_num = []

for i in self_num:
   not_self_num.append(d(i))

for j in self_num:
   if j not in not_self_num:
      print(j)

 

 

▶ list 사용없이 set 만 이용해주는 방법도 있습니다.

정답 3: if not in 이용

set() 원소 추가
append()가 아닌 add()를 씁니다.

def d(n):
   n = n + sum(map(int, str(n)))
   return n

not_self_num = set()

for i in range(1, 10001):
   not_self_num.add(d(i))

for j in range(1, 10001):
   if j not in not_self_num:
      print(j)