백준 1527 파이썬

 

(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