[프로그래머스] 다음 큰 숫자 python

문제

문제 설명
자연수 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 이하의 자연수 입니다.

 

풀이

$O(N)$으로 풀어야 한다.

처음엔 아래와 같이 직접 2진수 변환을 하고, list로 변환하여 1을 세는 등... 다양한 바보같은 짓을 했다 ! 

def convert(n, base=2):
    T = '0123456789ABCDEF'
    q, r = divmod(n, base)
    if q == 0:
        return T[r]
    else:
        return convert(q) + T[r]
    
def get_1cnt(string):
    return sum(map(int, list(string)))

결국 효율성 측면에서 떨어지는 코드였고, python의 장점을 살려 bin(), count() 메서드를 통해 구현했다.

• bin(int) : 2진수로 변환한 string을 반환한다. 앞에 '0b'는 2진수를 나타냄
• string.count(char or substring, start, end) : start 부터 end 까지 주어진 요소의 개수를 int로 반환한다.

코드

def solution(n):
    n_bin = bin(n).count('1')
    num = n+1
    while True:
        if num > n and n_bin == bin(num).count('1'):
            break
        num += 1
    
    return num