Algorithm : Level3. 다음 큰 숫자

October 12th, 2017

어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다.

  • N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.
  • 1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.

예를 들어, 78을 2진수로 바꾸면 1001110 이며, 78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다. N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.

내 풀이(문제 이해 실패..)

파라미터를 2진수로 바꾼 자릿 수 내에서의 1의 갯수로 문제를 잘못 이해했다…ㅠㅠ
(예를들어 78을 2진수로 변환하면 1001110. 즉, 7자리이므로 7자리 내에서의 1의 갯수)

생각대로 풀긴 풀었지만.. 다시 풀어야했다. 아래는 잘못 생각했을 때의 코드이다.

from itertools import permutations


def nextBigNumber(n):
    n_set = list()
    result_list = list()
    param = n

    while int(n) != 1:
        i = int(n) % 2
        n_set.append(i)
        n = int(n) / 2

    n_set.append(1)

    key_list = list(set(list(permutations(n_set))))

    for index, key in enumerate(key_list):

        list_key_sum = list()
        for inner_index, binary_num in enumerate(key):
            if binary_num == 1:
                list_key_sum.append(2 ** inner_index)

        result_list.append(sum(list_key_sum))

    result_list = sorted(result_list)

    print(result_list)

    try:
        if len(result_list) == 1 :
            print()
            return param

        else:
            for index, i in enumerate(result_list):
                if i == param:
                    print('현재값: {}\n 다음값: {}'.format(result_list[index], result_list[index + 1]))
                    return result_list[index + 1]

    except IndexError:
        print('input 값 {}이 최대 값입니다.'.format(param))
        return param


nextBigNumber(1000)

내 풀이

문제를 이해하고 푼 풀이

def nextBigNumber(n):

    bin_list_count = list(bin(n)[2:]).count('1')

    while True:
        n+=1
        if bin_list_count == list(bin(n)[2:]).count('1'):
            return n
        else:
            continue

print(nextBigNumber(78))

다른 사람 풀이

def nextBigNumber(n):
    cnt = bin(n).count('1')
    for biggerNum in range(n+1, 10000000):
        if cnt == bin(biggerNum).count('1'):
            return biggerNum

#아래 코드는 테스트를 위한 출력 코드입니다.
print(nextBigNumber(39028))

알게된 점

  1. bin(n)을 리스트로 굳이 안만들어도 count 가능.
  2. print(bin(n))을 해보면 ‘0b’가 앞에 붙는데 count할 때 됨.

siwon

$_$