[알고리즘/구현] 백준 BOJ 4673 셀프 넘버

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

입력

입력은 없다.

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

예제 입력 1

예제 출력 1

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

 

---

💡나의 문제 풀이

문제 해결 아이디어

• 10,000까지의 모든 정수에 대해, d(n)을 구해 리스트에 담는다. 이때 n은 생성자이다.
• 1부터 10,000까지의 수를 순회하며, 리스트에 해당 숫자가 포함되어 있는지 확인한다.
  • 이때, if in 을 사용하면, 시간 복잡도가 O(n)이므로 이를 최소화 하기 위해 이진 탐색을 사용한다.

 

---

작성 코드

• binary_search가 아닌 if in 을 사용해도 맞았던 문제, 심지어 sort를 하지 않아도 맞았던 문제.
• 숫자 크기가 크지 않아 시간이 오래 걸리지 않는 것 같다.

def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return 0

  
list = [] # 생성자가 만들어내는 수를 담는 리스트
for i in range(10000):
  sum = i
  for n in str(i):
    sum += int(n)
  list.append(sum)
  
list.sort()

# 이진 탐색으로 1부터 10,000까지 list에 존재하는지 탐색
for i in range(1,10000):
  if binary_search(i,list)==0:
    print(i)

 

 

---

 

답안 코드

백준 알고리즘 | 4673 : 셀프 넘버 (Python / 파이썬)

• set의 특징
  • 중복을 허용하지 않음
  • 순서가 없음(unordered) → 인덱싱으로 값을 얻을수 없다. 딕셔너리도 마찬가지.
  • set 자료형에 저장된 값을 인덱싱으로 접근하려면 리스트나 튜플로 변환해야 한다.
  • 집합(set)은 파이썬 2.3부터 지원하기 시작한 자료형으로, 집합에 관련된 것을 쉽게 처리하기 위해 만든 자료형으로, 합집합, 교집합, 차집합을 구하는데 유용함
• 점프 투 파이썬

natural_num = set(range(1,10001)) # 1~10000 까지 수의 집합 생성
generated_num = set()

for i in range(1,10001):
  for j in str(i):
    i += int(j)
  generated_num.add(i)

self_num = sorted(natural_num - generated_num) # 차집합 구한 후 오름차순 정렬
for i in self_num:
  print(i)

 

---

리뷰 및 점검

• 파이썬 자료구조에 따른 if in의 시간복잡도

# List
l = [1,2,3,4,5]

# Tuple
l = (1,2,3,4,5)

# Set
l = {1,2,3,4,5}

# Dictionary
l = {1:'a', 2:'b', 3:'c', 4:'d', 5:'e'}

• list, tuple → Average:O(n), 하나하나 순회
• set, dictionary → Average:O(1), worst: O(n) - 내부적으로 hash를 통해 저장하므로 접근 시간이 O(1)이지만 해쉬의 충돌이 많아 성능이 떨어지는 경우 O(n)