[edu] 가장 좋아하는 수 구하기

[가장 좋아하는 수]

철수는 4, 7 로만 이루어진 숫자를 좋아한다.

4, 7로만 이루어진 숫자중에 n번째 작은 숫자들까지 구하라.

example 1

input:

 2

output:

[4, 7]

 example 2

input:

 4

output:

[4, 7, 44, 47]

비트연산자 이용한 방법 (빠르다)

def get_fav(n):
    repeat = 1
    cur_size = 0
    size_prev = cur_size
    while True:
        cur_size += (2**repeat)
        if n <= cur_size:
            diff = n - size_prev
            break
        repeat += 1
        size_prev = cur_size

    base = bin(int("1" + "0" * repeat, 2) + diff - 1)
    return int(base[3:].replace("0", "4").replace("1", "7"))


def get_favs(n):
    nums = list()
    for i in range(1, n + 1):
        nums.append(get_fav(i))
    return nums


print(get_favs(int(input())))

순열 조합 이용한 방법(느리다)

def is_order(nums):
    size = len(nums) - 1
    result = 0
    for num in nums:
        if int(num) != 4 and int(num) != 7:
            return 0
        result += (10**size) * num
        size -= 1
    return result


def get_fav(max):
    fav = list()
    i = 1
    while True:
        permu = itertools.product(range(10), repeat=i)
        for nums in permu:
            num = is_order(nums)
            if num:
                fav.append(num)
                if len(fav) >= max:
                    return fav
        i += 1
    return list()


print(get_fav(int(input())))