금민수의 개수

풀이

 처음에는 순진하게도.. A에서 B까지 완전 탐색으로 접근했다. 하지만 시간초과 판정이 떴다. 시간 복잡도는 O(N)이지만 입력값의 범위가 10,000,000,000이므로 시간초과 판정이 당연하다. 생각을 조금 바꿔서 4와 7만을 이용해서 BFS로 완전 탐색을 수행해봤다. 시간 복잡도는 O(2^k) (k : 큐에 추가되는 원소 수)이지만 최악의 경우 O(2^10)이므로 문제를 해결할 수 있었다.

아래는 시간 제한이 1초인 입력 조건에 따른 시간 복잡도 예시이다.

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

from collections import deque
A, B = map(int, input().split())

queue = deque(['4','7'])
count = 0
while queue:
    x = queue.popleft()
    if int(x)<=B:
        if A<=int(x):
            count += 1
        queue.append(x+'4')
        queue.append(x+'7')
print(count)

시간복잡도 : O(2^k) (k : 큐에 추가된 원소 수)