from collections import Counter
# n까지의 숫자를 문자열로 변환하여 하나의 긴 문자열로 만듭니다.
def count_threes(n):
long_string = ''.join(str(num) for num in range(1, n+1))
counter = Counter(long_string)
return counter['3']+counter['6']+counter['9']
n = int(input())
result = count_threes(n)
print(result)나이브하게 그냥 문자열로 숫자를 이어 붙인 뒤 카운터로 세어서 더했다. 520ms의 결과를 얻었다.
그런데 생각해 보니 일정 구간마다 정해진 수의 3,6,9가 등장하기 때문에(균일하게 규칙적으로 분포) 하나하나 셀 필요가 전혀 없다.
def count_369(n):
count = 0
str_n = str(n)
length = len(str_n)
# 각 자리 수별로 3, 6, 9의 개수를 계산
for digit in range(length):
power_of_ten = 10 ** digit
next_power_of_ten = power_of_ten * 10
right_part = n % power_of_ten
current_digit = (n // power_of_ten) % 10
left_part = n // next_power_of_ten
# 3, 6, 9가 current_digit 자리에 올 수 있는 경우의 수를 계산
count += left_part * power_of_ten
if current_digit > 3:
count += power_of_ten
elif current_digit == 3:
count += right_part + 1
count += left_part * power_of_ten
if current_digit > 6:
count += power_of_ten
elif current_digit == 6:
count += right_part + 1
count += left_part * power_of_ten
if current_digit > 9:
count += power_of_ten
elif current_digit == 9:
count += right_part + 1
return count
n = int(input())
print(count_369(n))
함수 정의 및 초기 설정
def count_369(n):
count = 0
str_n = str(n)
length = len(str_n)
함수 count_369는 숫자 n을 인자로 받아서 3, 6, 9의 개수를 세는 역할을 한다. count는 3, 6, 9의 개수를 저장할 변수이다. str_n은 숫자 n을 문자열로 변환한 값이며, length는 그 문자열의 길이를 저장한다. 예를 들어 n = 45일 때, str_n은 "45"가 되고 length는 2가 된다.
각 자리 수별로 3, 6, 9의 개수를 계산
for digit in range(length):
power_of_ten = 10 ** digit
next_power_of_ten = power_of_ten * 10
right_part = n % power_of_ten
current_digit = (n // power_of_ten) % 10
left_part = n // next_power_of_ten
각 자리 수(digit)를 순회하며, 해당 자리 수에서 3, 6, 9가 나오는 경우를 계산한다. 예를 들어, 첫 번째 반복에서 digit = 0일 때:
power_of_ten은1(10 ** 0).next_power_of_ten은10(10 ** 1).right_part는n % power_of_ten즉45 % 1이므로0.current_digit은(n // power_of_ten) % 10즉(45 // 1) % 10이므로5.left_part는n // next_power_of_ten즉45 // 10이므로4.
3이 current_digit 자리에 올 수 있는 경우의 수 계산
count += left_part * power_of_ten
if current_digit > 3:
count += power_of_ten
elif current_digit == 3:
count += right_part + 1
현재 자리 수에 3이 올 수 있는 경우를 계산한다. left_part에 power_of_ten을 곱한 값을 더하여 왼쪽 부분에서 발생할 수 있는 모든 경우의 수를 더한다. current_digit이 3보다 큰 경우, power_of_ten을 더하여 현재 자리 수에서 3이 올 수 있는 경우를 더한다. 예를 들어, digit = 0일 때 current_digit이 5이므로 count에 1을 더한다.
6이 current_digit 자리에 올 수 있는 경우의 수 계산
count += left_part * power_of_ten
if current_digit > 6:
count += power_of_ten
elif current_digit == 6:
count += right_part + 1
현재 자리 수에 6이 올 수 있는 경우를 계산한다. 이 부분은 3의 경우와 같은 방식으로 작동한다. digit = 0일 때 current_digit이 5이므로 이 부분에서는 추가되지 않는다.
9이 current_digit 자리에 올 수 있는 경우의 수 계산
count += left_part * power_of_ten
if current_digit > 9:
count += power_of_ten
elif current_digit == 9:
count += right_part + 1
현재 자리 수에 9가 올 수 있는 경우를 계산한다. 이 부분도 3과 6의 경우와 같은 방식으로 작동한다. digit = 0일 때 current_digit이 5이므로 이 부분에서도 추가되지 않는다.
두 번째 자리 수에 대해 반복
다음으로 digit = 1일 때:
power_of_ten은10(10 ** 1).next_power_of_ten은100(10 ** 2).right_part는45 % 10이므로5.current_digit은(45 // 10) % 10이므로4.left_part는45 // 100이므로0.
이 경우도 각 자리 수에 대해 같은 논리가 적용된다. current_digit이 4이므로 3이 올 수 있는 경우를 계산할 때는 count에 10을 더한다.
최종 결과 반환
return count
모든 자리 수에 대해 계산이 끝나면 최종적으로 3, 6, 9의 개수를 반환한다.
전체 코드 실행 결과
n = 45를 입력했을 때 각 자리 수에서 3, 6, 9가 나올 수 있는 경우의 수를 계산하여 최종적으로 count는 14가 된다. (3이 1자리 수에 올 수 있는 경우 4번, 6이 1자리 수에 올 수 있는 경우 4번, 9이 1자리 수에 올 수 있는 경우 4번, 3이 10자리 수에 올 수 있는 경우 1번, 6이 10자리 수에 올 수 있는 경우 1번, 9이 10자리 수에 올 수 있는 경우 1번으로 총 14번).