정수로 이루어진 범위가 주어졌을 때, 그 범위 안에 포함된 특수 숫자(special number)의 개수를 찾아야 한다고 가정해 봅시다. 특수 숫자란 십진수 표현에서 한 자리만 가지는 양의 정수를 의미합니다. 두 자리 이상의 숫자라도 자신의 자릿수로 나누어 떨어지고, 그 몫 역시 특수 숫자라면 특수 숫자로 분류할 수 있습니다. 즉, 주어진 범위(left_limit, right_limit) 내에 존재하는 특수 숫자의 총 개수를 반환하는 것이 목표입니다.
예를 들어 입력이 left_limit = 5, right_limit = 30이라면 출력은 13이 됩니다.
이 범위에 포함되는 특수 숫자는 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 24, 28로 총 13개입니다.
문제 해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다 −
- 만약 right_limit < 10이라면
- right_limit - left_limit + 1을 반환합니다
- len_right := right_limit을 문자열로 변환했을 때의 길이
- number_list := [0,1,2,3,4,5,6,7,8,9,10,12,14,16,18]
- j를 2부터 len_right + 1까지 반복합니다
- number_list의 각 요소 k에 대해
- temp1 := k * j
- temp1을 문자열로 변환한 길이가 j와 같다면
- number_list의 끝에 temp1을 추가합니다
- 그렇지 않고 len(str(temp1)) > j라면
- 반복문을 종료합니다
- number_list의 마지막 요소가 right_limit보다 크거나 같다면
- 반복문을 종료합니다
- number_list의 각 요소 k에 대해
- number_list에서 중복 값을 제거한 뒤 정렬합니다
- count := 0으로 초기화합니다
- number_list의 각 요소 temp2에 대해
- temp2가 left_limit 이상이고 right_limit 이하라면
- count를 1 증가시킵니다
- temp2가 left_limit 이상이고 right_limit 이하라면
- count를 반환합니다
예제
더 나은 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다 −
def strange(left_limit, right_limit):
if right_limit < 10:
return right_limit - left_limit + 1
len_right = len(str(right_limit))
number_list = [0,1,2,3,4,5,6,7,8,9,10,12,14,16,18]
for j in range(2, len_right + 1):
for k in number_list:
temp1 = k*j
if len(str(temp1)) == j:
number_list.append(temp1)
elif len(str(temp1)) > j:
break
if number_list[len(number_list)-1] >= right_limit:
break
number_list = list(set(number_list))
count = 0
for temp2 in number_list:
if temp2 >= left_limit and temp2 <= right_limit:
count = count + 1
return count
print(strange(5, 30))입력
5, 30
출력
13
알고리즘 설명
이 알고리즘의 핵심은 이미 알려진 작은 특수 숫자들(0~9와 10, 12, 14, 16, 18)을 기준으로 삼고, 각 숫자에 자릿수를 곱해가며 더 큰 특수 숫자를 생성해내는 것입니다. 예를 들어 5는 한 자리 특수 숫자이므로, 두 자리 숫자 10(= 5 × 2) 역시 특수 숫자가 됩니다. 이렇게 생성된 숫자들을 주어진 범위와 비교하여 개수를 세면 되며, 생성되는 특수 숫자의 개수가 매우 적기 때문에 시간 복잡도 측면에서도 매우 효율적입니다.