[Programmers] 다음 큰 숫자.

Description

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항

• n은 1,000,000 이하의 자연수 입니다.

Solve

def solution(n):
    bit_of_n = bin(n)
    bit_of_n_count_1 = bit_of_n.count('1')
    _limit_ext = n

    while True:
        _limit_ext += 1

        if bin(_limit_ext).count('1') == bit_of_n_count_1:
            return _limit_ext

1. 입력받은 n의 이진수와 이진수에 대한 '1'의 갯수를 카운트한 값을 구한다.
2. n의 다음 값을 구하기 위해 n의 값을 따로 저장해둔다.
3. while문을 돌면서 따로 저장해둔 값에다가 1을 더하면서 확장해나간다.
   1. n부터 순차적으로 증가하므로 조건 2를 체크하는 과정이다.
   2. 문제에서 요구한 조건 3이 만족하는지 if 문에서 검증한다.
      1. 만족하는 경우 return

Notes

 def solution(n):
     bit_of_n = bin(n)
     bit_of_n_count_1 = bit_of_n.count('1')

     for x in range(n + 1, 1_000_000 - n):
         if bin(x).count('1') == bit_of_n_count_1:
             return x

처음엔 위와 같이 n과 문제에서 n에 대해 제한된 사이즈를 줘서 for문으로 돌렸는데 효율성 부분에서 통과하지 못했다.