LeetCode 1680

문제 링크

문제 설명

숫자 n이 주어지고, 1부터 n까지 binary로 변환한 숫자를 이어붙인 숫자를 10**9 + 7로 나눈 숫자를 출력하는 문제.

example :

n = 3
bin(1) = 1
bin(2) = 10
bin(3) = 11

Thus, 
print(int(11011,2)) == 27

문제 풀이 & solution

풀이 자체는 간단했다. 초기값 1(arr == 1)을 넣어주고, 2부터 n까지

1. 기존 결과(arr)에 다음 값(i)이 들어갈 길이만큼의 binary를 밀어줌.
2. 다음 값을 더해줌.
3. 10**9 + 7로 숫자를 나눠줌.

이 과정을 반복한 결과 다음과 같은 식을 짤 수 있다.

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        arr = 1
        for i in range(2,n+1):
            arr = ((arr<<len(bin(i))-2) + i)%1000000007
        
        return arr

cf. 이런 선형적인 방법보다 더빠르게 푸는 방법이 존재하는 듯 하다.(정확하지 않음.)
이 식을 썼을 때 1599ms의 시간이 들었고, python의 한계인지는 모르겠지만 더 빠른 결과가 나온 것이 있었다.

잡담.

• 컨버티드 리뷰에 대해 글을 쓰고 있는데 허공에서 해엄치는 기분이다.. 나름대로 기준을 잡고 글을 쓰고 있는데도 난이도가 장난이 없다.
• notion API는 잠정 중단중.. front에 대해 하루에 조금씩 시간을 들여서 공부중인데 역시 흥미가 없어서 그런지 겁나 진도가 나가질 않는다..(그냥 니콜라스를 따라갈까?..)