boj - 1065: 한수 (python)

풀이계획

• 편법 : 2자리수까지는 모두 한수

코드

• 제출

number = int(input())
cnt = number

def is_hansu(cnt):
  if number<100:
    pass
  else:
    #한수가 아니면 cnt에서 뺸다.
    for i in range(100,number+1):
      data = [int(j) for j in str(i)]
      if data[0]-data[1] != data[1]-data[2]:
        cnt -= 1
  return cnt

print(is_hansu(cnt))

• 확장성을 고려한 개선코드, (1000 이상의 input 입력에 대한)

number = int(input())
cnt = number

def is_hansu(cnt):
  if number<100:
    # 2개 원소까지는 무조건 한수이다.
    pass
  else:
    # 이후부터는 한수가 아니면 cnt에서 뺀다.
    for i in range(100,number+1):
      data = [int(j) for j in str(i)]
      # 반복횟수가 정해져있다(for) : len(data)-1
      gap = data[0]-data[1]
      for k in range(1,len(data)-1):
        # print(1)
        if data[k]-data[k+1] != gap:
          cnt -= 1
          break
  return cnt

print(is_hansu(cnt))

결과

• time complexity = o(n^2)
  - 모든 수를 원소별로 검사해야 하기 때문에 (한수정의 충족 여부) 불가피하게 n^2가 소요된다.
• space complexity = o(n)

시사점

• break 사용의 중요성

더 고민할 사항

• 함수를 더 효과적으로 사용할 수 있는 방법이 있는 것인지 (함수 사용 카테고리에 있는 문제이다)