[BOJ][⚪1][백준#01527] 금민수의 개수

문제 출처

BAEKJOON Online Judge #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

출력

2

예제 2

입력

11 20

출력

0

예제 3

입력

74 77

출력

2

예제 4

입력

1000000 5000000

출력

64

My Sol

def nextDeci(arr):
    return [*[i*10+4 for i in arr], *[i*10+7 for i in arr]]

ret = [[4, 7]]
S, E = map(int, input().split())
sl, el = len(str(S)), len(str(E))
for n in range(1, len(str(E))):
    ret.append(nextDeci(ret[-1]))

cnt1 = 0
for i in range(sl-1):
    cnt1 += 2 ** (i + 1)
for n in ret[sl-1]:
    if S > n: cnt1 += 1

cnt2 = 0
for i in range(el-1):
    cnt2 += 2 ** (i + 1)
for n in ret[el-1]:
    if E >= n: cnt2 += 1

print(cnt2 - cnt1)

이전 수에서 4와 7을 붙인 뒤 배열을 합치는 방식을 사용하였다.

1. 4와 7로 구성된 배열을 ret 배열에 넣는다.
2. 이전 인덱스의 배열의 각 요소에 4를 붙인 배열과 7을 붙인 배열을 합치는 함수를 만든다.
3. 이를 E의 길이만큼 반복한다.
4. 작은 수와 큰 수를 ret에서 조회해 만족하는 개수를 구하고, 이 차를 계산한다.

관건은 앞에서 불필요한 연산을 하지 않고 같은 길이의 ret의 배열에서 브루트포스로 크기를 비교해 확인하는 것이다.

그리고 앞의 숫자의 비교에서는 n을 포함해서는 안 되는데, 이는 이 중간 영역에서 서로의 양 끝값을 포함하기 때문이다. 때문에 S는 n보다 큰 경우만 cnt1을 올리고, E는 n보다 크거나 같은 경우 cnt2를 올린다.

결과

맞았습니다!!