[BOJ/Python] 1527_금민수의 개수

문제 출처:https://www.acmicpc.net/problem/1527

1527번: 금민수의 개수

 

문제

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력한다.

예제 입력 1

1 10

예제 출력 1

2

예제 입력 2

11 20

예제 출력 2

0

예제 입력 3

74 77

예제 출력 3

2

예제 입력 4

1000000 5000000

예제 출력 4

64

---

풀이

 

큐를 이용하여 문제를 해결하였다.

A<= (4와 7로만 이루어진 수) <=B 를 만족하는 (4와 7로만 이루어진 수)의 개수를 찾는 문제이다.

풀이는 다음과 같다.

 

1. 큐를 생성하여 4와 7을 집어넣는다.
2. 큐에서 수를 하나 꺼낸다. (맨 처음 꺼내는 수는 4이다.)
3. 꺼낸 수가 A보다 작거나 같다면 해당 수에 4와 7을 붙인 수를 큐에 넣는다. (44, 47)
4. 그리고 여기서 꺼낸 수가 A와 같다면 count를 1 더해준다.
5. 그리고 만약 꺼낸 수가 A보다 크고 B보다 작거나 같다면 count를 1 더해주고, 여기서 B보다 작다면 꺼낸 수에 4와 7을 붙여서 큐에 넣는다.
6. 이 과정을 큐에 수가 존재하는 동안 반복한다.
7. 최종적으로 count를 출력하면 A이상 B이하의 4와 7로만 이루어진 수의 개수를 구할 수 있다.

코드는 다음과 같다.

 

import sys
import collections
 
a,b = map(int,sys.stdin.readline().split())
 
queue = collections.deque()
queue.extend([4,7])
count = 0
 
while queue:
    num = queue.popleft()
    if num<=a:
        queue.extend([num*10+4, num*10+7])
        if num==a:
            count+=1
    elif num<=b:
        count+=1
        if num<b:
            queue.extend([num*10+4, num*10+7])
    
 
print(count)