boj - 4673: 셀프 넘버 (python)

풀이계획

• 생성자에 의해 생성된 값을 리턴하는 기능을 함수로 묶는다.
• linear search를 통해 주어진 범위까지 오름차순으로 값을 생성한다.
• 별도 주어진 범위의 데이터 리스트를 만들어 그 내에서 생성자에 의해 생성된 값을 지워나간다. [xor, 배타적, 여집합 구하는 문제]

코드

def creator(number):
  # 생성자를 통해 생성된 값을 리턴한다.
  value = number
  while number != 0:
    value += number % 10
    number = number // 10
  return value

data = [i for i in range(1,10001)]
for j in range(1,10001):
  created = creator(j)
  if created in data:
    data.remove(created)

for k in data:
  print(k)

막히거나 고민한 점

• time complexity = o(n)
• space complexity = o(n)
• space complexity를 줄이는 방법이 있을지 조금 더 고민이 필요하다.

새로 알게된 것

• 자릿수의 값을 더하는 방법을 하나 더 깨닫게 되었다. (원래 아래 방법을 썼다)
• 아직 공부 초반이라 더 많은 방법이 있을 것 같다.

number = 124
data = [int(i) for i in str(number)]
sum(data)

풀이 시행착오

• 처음에 수학적으로 아래와 같이 접근했다.
• 데이터 사이즈가 커지면서 코드확장성이 확보되지 않고 11a+2b -> 101a+11b+2c -> 1001a+101b+11c+2d와 같이 계속 코드 수정이 필요한 문제가 있어 개선방법을 찾았다.

def printer():
  data = list(range(1,10001))
  for i in range(10):
    for j in range(10):
      for k in range(10):
        for m in range(10):
          value = 1001*i+101*j+11*k+2*m
          if value in data: # 생성자로 여러번 참여할 수 있으니까.
            data.remove(value)
  for number in data:
    print(number)

printer()

미스터리

• 4중 for문으로 작성했을 때보다, 풀이코드로 채점했을 때 시간이 더 늘어났다. 이유를 알지 못하겠다.