(1) 처음 내 코드 -> 시간초과
a,b = map(int,input().split())
cnt = 0
s1="4"
s2="7"
for i in range(a,b+1):
s = str(i)
bool=True
for j in s:
if j==s1 or j==s2:
continue
else:
bool=False
break
if bool==True:
cnt+=1
print(cnt)입력이 1보다 크고, 1,000,000,000보다 작거나 같은 자연수로, 코드 제출하기 버튼을 누르면서도 뭔가 시간초과가 날거 같았다.
(2) 문제 해결 후 내 코드 -> product 사용
from itertools import product
a,b = map(int,input().split())
cnt = 0
key = []
s = []
for i in range(len(str(a))):
key.append([4,7])
for i in range(len(str(a)),len(str(b))+1):
if i!=len(str(a)):
key.append([4,7])
set = list(product(*list(key)))
for i in set:
string=""
for j in i:
string+=str(j)
s.append(int(string))
for i in s:
if a<=i and i<=b:
cnt+=1
print(cnt)cartesian곱을 이용하여 모든 경우의 수를 구하기 위해 itertools의 product 모듈을 사용하였다. 먼저, 빈 리스트에 시작 범위의 자릿수만큼 [4,7]을 추가해준다. 그 뒤 for문을 돌며, key 리스트에 있는 값들끼리 카테션 곱셈을 수행하고, 이 값들을 string으로 바꿔주는 작업을 수행한다. 마지막 for문에선 처음에 입력으로 받은 a와 b의 범위 사이에 해당 string이 존재한다면 카운트를 증가시켜주고 이 값을 출력해주었다.
ex)
input : 1 100
set -> 각 자릿수의 숫자가 set 형태로 리스트 안에 들어가있음.
[(4,), (7,)]
[(4, 4), (4, 7), (7, 4), (7, 7)]
[(4, 4, 4), (4, 4, 7), (4, 7, 4), (4, 7, 7), (7, 4, 4), (7, 4, 7), (7, 7, 4), (7, 7, 7)]
s -> 위의 값들이 문자열 형태로 리스트 안에 들어가있음.
[4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777]
output : 6
(3) 코드 피드백 후 내 코드 -> bfs 사용
from collections import deque
a,b = map(int,input().split())
cnt=0
queue= deque()
queue.append(4)
queue.append(7)
while queue:
q = queue.popleft()
if q<=b:
if a<=q:
cnt+=1
queue.append(q*10+4)
queue.append(q*10+7)
print(cnt)bfs를 사용하면 간단하게 풀 수 있다.
ex)
input : 1 100
queue
(1) 초기 queue값
4 7
(2) while문 안에서의 queue값
7 44 47
44 47 74 77
47 74 77 444 447
74 77 444 447 474 477
77 444 447 474 477 744 747
444 447 474 477 744 747 774 777
447 474 477 744 747 774 777
474 477 744 747 774 777
477 744 747 774 777
744 747 774 777
747 774 777
774 777
777
output : 6