내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/12911

n이 10만 이하의 자연수입니다. 10만은 2진법으로 나타냈을때 1 1000 0110 1010 0000이고 길이는 17입니다.

우리가 찾아야하는 수는 n보다 크고 이진수로 나타냈을때 1의 갯수가 같은 수 중에 가장 작은 수입니다. 나올 수 있는 최악의 경우를 나이브하게 생각해봅시다.

길이가 17인 이진수에서 1의 갯수는 많아봐야 17개입니다. (10만을 넘기 때문에 실제론 1의 수가 더 적습니다.) 따라서 우리가 찾아야 하는 최악의 수는 1의 갯수가 17개인 n보다 큰 가장 작은 수입니다. 가능한 수 중에서 가장 작은 수는 11 1111 1111 1110 따위가 되겠죠. 이 값이래봐야 50만 근처입니다.

즉 나오지도 않는 최악중 최악의 경우에도 우리가 찾아봐야 하는 수의 갯수는 50만개이고 이 정도면 충분히 시간안에 탐색 할 수 있습니다. 따라서 n보다 큰 수를 모두 이진수로 바꿔가며 1의 수를 카운팅하고 1의 수가 같을때 바로 탐색을 끝냈습니다.

def solution(n):
    c = str(bin(n)[2:]).count('1')
    print(str(bin(100000)))
    while True:
        n += 1
        if str(bin(n)[2:]).count('1') == c:
            return n