[백준] 1527 - 금민수의 개수

문제

 

 

백준 1527번 금민수의 개수

➡️문제 링크 : https://www.acmicpc.net/problem/1527

 

문제 풀이

 

4와 7로만 이루어진 수를 찾을 때, 작은 문제가 큰 문제의 최적해를 찾을 수 있는 그리디나 DP 도 아니고 탐색 종류도 아니각 자리 수에서 4와 7의 포함 가능 여부를 확인하는 것도 왼쪽 다음 자리 수의 A,B 내 범위에 따라 달라지는 복잡한 양상을 띄고 있어 전수조사 즉 브루트포스를 해야겠다고 생각했다. 

처음 코드에서는 a에서 b까지의 수를 str() 함수를 통해 변환한 후, 차례대로 문자열의 요소를 확인하며 4나 7이 아닌 수일 경우 곧바로 False를 리턴하는 방식으로 함수를 작성하였다.

그러나 10억 범위의 수를 갖는 상황에서, 매우 단순한 이런 방법으로는 당연하게도 시간 초과가 발생하였다.

 

# 오답 코드 : 시간초과

a,b=map(int,input().split(' '))
ans=0

for i in range(a,b+1):
    flag=1
    for j in str(i):
        if j not in ['4','7']:
            flag=0
            break 
    if flag:
        ans+=1

print(ans)

 

 

이후 생각한 다른 방법은 1의 자리부터 9의 자리까지 자리(단위)를 늘려가면서 4와 7만의 순서 있는 조합을 확인하는 것이었다. 그런데 각 자리수를 늘려가면서 4와 7만을 가진 수의 모든 경우를 어떻게 찾을 수 있을지가 의문이었다. 

 

이후 다음과 같은 블로그 글을 참고하여

➡️참고한 블로그 링크 : https://velog.io/@hygge/Python-%EB%B0%B1%EC%A4%80-1527-%EA%B8%88%EB%AF%BC%EC%88%98%EC%9D%98-%EA%B0%9C%EC%88%98-Brute-Force

[Python] 백준 1527 금민수의 개수 (Brute Force)

 

python itertools의 product()를 사용하면 중복을 허용하는 순서집합을 구할 수 있다는 것을 새로 알게 되었다.

 

python의 itertools는 주요하게 다음의 4가지 조합형 반복 함수를 제공한다.

 

itertools의 조합형 이터레이터

product()	permutations()
데카르트 곱, 중복 O, 순서 O 용례) product('ABCD', repeat=2)	순열, 중복 X, 순서 O 용례) permutations('ABCD', 2)
combinations()	combinations_with_replacement()
조합, 중복 X , 순서 X 용례) combinations('ABCD',2)	조합, 중복 O, 순서 X 용례) combinations_with_replacement('ABCD', 2)

 

4와 7을 중복하여 각 자리수에 따른 순서 있는 모든 조합의 수를 구하고자 하므로, product() 함수를 사용하여 각 자리수에 따른 조합의 수를 구할 수 있었다!

 

a의 자리수와 b의 자리수를 각각 low, high로 두고, 각 자리수만큼의 데카르트 곱을 구해 튜플 리스트로 반환되는 모든 경우의 수를 lst 라는 변수에 둔다. 이후 lst를 반복하며 cand 라는 수로 변환하고, cand가 a와 b 사이일 경우 ans에 1을 더하고, product()에서 반환하는 튜플들의 순서는 오름차순이므로 cand가 b보다 큰 경우 flag에 1을 넣어 더 이상의 반복이 이루어지지 않도록 하였다. 

 

 

코드

# 브루트 포스
from itertools import product
a,b=map(int,input().split(' '))
ans=0

# 1의 자리부터 9의 자리까지 자리 단위를 늘려가면서 
low=len(str(a))
high=len(str(b))
flag=0
for i in range(low,high+1):
    lst = product(['4','7'],repeat = i)
    for c in lst:
        cand=int(''.join(c))
        if a<=cand<=b:
            ans+=1
        elif cand>b:
            flag=1
            break
    if flag:
        break

print(ans)