금민수의 개수 ( 1527 번 )

1527번: 금민수의 개수

 

---

🧠 알고리즘

• 브루트포스(Brute Force) + 순열 생성 (itertools.product)

 

✔️ 동작 방식

• 구간 [a, b]의 경계값 a, b의 자릿수를 구한다. (len_a, len_b)
• 해당 자릿수의 모든 러키 넘버 후보를 생성한다
• 생성된 숫자를 정수로 변환한 뒤, 구간 [a, b]에 속하면 answer를 +1 증가시킨다.

---

 

🧾 코드

import sys
from itertools import product

def _main(a, b):
    answer = 0
    len_a = len(str(a))
    len_b = len(str(b))

    for repeat_num in range(len_a, len_b + 1):
        for pd in product(['4', '7'], repeat = repeat_num):
            now_pd = int(''.join(pd))
            if (now_pd >= a) and (now_pd <= b):
                answer += 1

    return answer


a, b = map(int, sys.stdin.readline().rstrip().split())
print(_main(a, b))

---

 

⏱️ 시간 복잡도

for pd in product(['4', '7'], repeat = repeat_num) : 중복 순열, 자릿 수 만큼 조합 출력 ( 지수형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 지수형 시간 복잡도 ( O(2 ** n) )