BAEKJOON 4673 - Self Number

셀프 넘버

---

◎ Problem Definition

4673번: 셀프 넘버

---

◎ Implementation

1. Problem Type 

 - Implementation, Brute Force (실버 5)

2. Problem Analysis

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

- d(n) : n + n의 각 자리수  (n : int, n>0)

• 51의 생성자 : 39  (∵ 39 + 3 + 9 = 51)
• 101의 생성자 : 91, 100  (∵ 91 + 9 + 1 = 101; 100 + 1 = 101)

 

셀프 넘버 : 생성자가 없는 숫자

• 1000보다 작은 셀프 넘버 : 총 13개 (1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97) 

3. Solution_1 (☆초기 접근)

Brute Force하게 접근했다. dictionary 형태로 check 변수를 선언하고 {index, 0}으로 초기화한다. 1부터 순차적으로 생성자를 계산하여 check의 value값을 1로 변경한다. 각 숫자의 자리수는 <10 이면 한 자리수, <100이면 두 자리수, <1000이면 세 자리수 의 방법으로 구분했으며, %와 // 연산을 통해 각 자리수 숫자를 추출했다. → 이 부분은 조금 더 세련되게 구현하고 싶다. 

마지막으로 check의 value값을 한 번씩 검색하여 '0'의 값을 갖는 항목의 key 값을 출력한다.  

▶ 완성 코드 

# BAEKJUN 4673 - Self Number
# Python Code
# Type : Brute Force, Implementation
# Date : Jan. 10. 2022
# written by LemonSoda

N = 10000
check = {}
for i in range(1, N+1):
    check[i] = 0

for i in range(1, N+1):
    if i < 10 and i+i < (N+2):
        check[i+i] = 1
    elif i < 100 :
        tmp = 0
        tmp = i + i%10 + i//10
        if tmp < N+2:
            check[tmp] = 1 
    elif i < 1000 : 
        tmp = 0
        tmp = i + i//100 + (i%100)//10 + i%10 
        if tmp < N+2:
            check[tmp] = 1
    elif i < 10000 : 
        tmp = 0 
        tmp = i + i//1000 + (i%1000)//100 + (i%100)//10 + i%10
        if tmp < N+2:
            check[tmp] = 1
        
for i in range(1, N+1):
    if check[i] == 0:
        print(i)

▶ 성능 

4. Solution_2 (★공개된 다른 코드 참조)

▶ Reference

4673 백준 셀프 넘버 [파이썬]

▶ 완성 코드

string으로 변환하여 한 자리씩 숫자를 읽어오는 방법을 사용했다. 코드가 훨씬 깔끔해졌다. 단, 형변환 반복으로 수행시간이 길어진 것 같다. set을 이용하여 차를 구하고 sorted 시킨 부분도 정말 깔끔하다. 

# BAEKJUN 4673 - Self Number
# Python Code
# Type : Brute Force, Implementation
# Date : Jan. 10. 2022
# Reference : https://blog.naver.com/rnvl27/222607208027
# written by LemonSoda

N = 10001
num = set(range(1,N+1))  # 자연수 set
new = set() # 생성자

for i in range(1, N+1):
    for j in str(i):    # 정수 i를 string list로 변환하여 자리수 만큼 반복
        i += int(j) 
    new.add(i)

check = sorted(num - new)
for i in check: 
    print(i)

▶ 성능

---

◎ Results

- dictionary, set, tuple 등 다양한 자료구조 형태에 익숙해져서 상황별로 적합한 자료형을 선택하도록 하자.

- 반복항을 제거할 때는 set을 사용하면 간편하다.

-  str 데이터의 list 구조를 활용하면 때로는 쉽게 접근할 수 있다. string과 친해지면 사용할 수 있는 func의 자유도가 높아진다. 

- 

- 코딩 능