문제

자연수 n 다음으로 큰 수를 다음과 같이 정의한다.
1) n 보다 큰 자연수이다.
2) 이진수로 변환했을때 n과 1의 갯수가 같다.
3) n 1,2 를 만족하는 수중에서 가장 작은 수 이다.

접근법

경우의 수를 나누는데 꽤 애를 먹었다. 이진수로 바꾸는 문법 bin에대한 사용과 이진수 십진수 변환에 대한 이해를 잘 하고 있는지 묻는 문제였다. 다른사람의 풀이를 보고 좀 현타가왔다.

코드

def solution(n):
    binary_n = bin(n)[2:]
    # print(binary_n)
    if '0' not in binary_n: # 1111
        return int('10' + binary_n[:-1], 2)
    if binary_n.count('1') == 1: # 100 or 1000 or 10 or 1
        return 2*n
    list_n = list(binary_n)
    cnt = -1
    for i in range(len(list_n)-1, -1, -1):
        if list_n[i] == '1':
            list_n[i] = '0'
            for j in range(i-1, -1, -1):
                if list_n[j] == '1':
                    list_n[j] = '0'
                    list_n[cnt] = '1'
                    cnt -= 1
                    if j == 0:
                        return int('1'+''.join(list_n), 2)
                elif list_n[j] == '0':
                    list_n[j] = '1'
                    # print(list_n)
                    return int(''.join(list_n), 2)

다른사람풀이

def nextBigNumber(n):
    c = bin(n).count('1')
    for m in range(n+1,1000001):
        if bin(m).count('1') == c:
            return m