백준 4673번 셀프 넘버 (Python)

출처

백준 4673 셀프 넘버

---

정답

N = 10000
candidates = set([i for i in range(1, N + 1)])
generated_numbers = set()
for i in range(N):
  for s in str(i):
    i += int(s)
  generated_numbers.add(i)

self_numbers = candidates - generated_numbers
for i in sorted(self_numbers):
  print(i)

---

문제

---

입출력

---

풀이

0. 전략

생성자 (제너레이터) 정의

코드업 1615번 셀프 넘버 (Python)

 

구현전략

1) 주어진 범위 (1 ~ 10000) 내의 모든 수는 셀프 넘버가 될 수 있는 후보이다 (candidates)
2) 주어진 범위 (1 ~ 10000) 내에 생성자가 있는 수를 확인한다 
   - d(1) ~ d(9999) 호출 
   - d(1) ~ d(9999) 로 생성된 수 즉, 셀프 넘버가 아닌 수를 generated_numbers에 추가한다 
   ※ d(K) 는 항상 K 보다 크기 때문에 d(b) 는 호출할 필요가 없다 
3) 셀프 넘버 후보에서 셀프 넘버가 아닌 수를 제외하여 셀프 넘버를 구한다 (self_numbers)
   - set 을 이용한 차집합으로 처리 
4) 셀프 넘버를 오름차순으로 정렬 후 출력한다 

1. 문제/입력값에 의한 초기 설정

# 셀프 넘버를 구할 범위 N
N = 10000
# 셀프 넘버가 될 수 있는 candidates 집합을 생성, 초기화한다  
candidates = set([i for i in range(1, N + 1)]) # (1 ~ 10000)
# 생성자가 있는 수 즉, 셀프 넘버가 아닌 수의 집합을 선언한다
generated_numbers = set() # ()

2. 생성자가 있는 수를 확인하는 알고리즘

# ~ d(9999) 호출 
for i in range(N):
  # 입력된 숫자를 문자열로 변경 후 
  # 각 자리수를 원래의 수에 더한다
  for s in str(i):
    i += int(s)
  # 생성된 수는 셀프 넘버가 아닌 수의 집합에 추가한다 
  generated_numbers.add(i)
# 셀프 넘버 후보에서 셀프 넘버가 아닌 수를 제외하여 셀프 넘버를 구한다 
self_numbers = candidates - generated_numbers

3. 정답 출력

# 10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.
# 셀프 넘버를 정렬 후 출력한다  
for i in sorted(self_numbers):
  print(i)

---

셀프 넘버 예시

1) N = 12

회차	generated_numbers	candidates - generated_numbers
d(1)	2	(1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
d(2)	4	(1, 3, 5, 6, 7, 8, 9, 10, 11, 12)
d(3)	6	(1, 3, 5, 7, 8, 9, 10, 11, 12)
d(4)	8	(1, 3, 5, 7, 9, 10, 11, 12)
d(5)	10	(1, 3, 5, 7, 9, 11, 12)
d(6)	12	(1, 3, 5, 7, 9, 11)
d(7)	14	(1, 3, 5, 7, 9, 11)
d(8)	16	(1, 3, 5, 7, 9, 11)
d(9)	18	(1, 3, 5, 7, 9, 11)
d(10)	11	(1, 3, 5, 7, 9)
d(11)	13	(1, 3, 5, 7, 9)

셀프 넘버 : 1, 3, 5, 7, 9

---