다음 큰 숫자

프로그래머스 - 다음 큰 숫자

문제 설명

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

입출력 예

풀이

def solution(n):
    count_of_one = format(n, 'b').count('1')

    while True:
        n += 1
        if count_of_one == format(n, 'b').count('1'):
            return n

해결 과정

이 문제의 해결을 위한 전체적인 흐름은 다음과 같다.

1. n을 이진수로 바꿨을 때 1의 개수를 구한다.
   이는 파이썬에서 제공하는 format 함수(혹은 bin 함수)를 사용하여 이진수로 변환한 뒤, count 메서드를 사용하여 '1'의 개수를 구하면 된다.

2. n을 1 증가시킨다.

3. 2번을 통해 얻은 n을 이진수로 변환해 1의 개수를 구한다.

4. 3번의 값이 1번의 값과 동일한지 비교한다.
   4-1. 동일하다면 n을 반환한다.
   4-2. 아니라면 1번으로 돌아간다.

다른 사람의 풀이

from collections import Counter


def number_to_binary(n):
    bin_num = ''

    while n:
        modNum = n % 2
        bin_num += str(modNum)
        n = n // 2

    return bin_num


def count_one(n):
    return Counter(n)['1']


def solution(n):
    count_of_one = count_one(number_to_binary(n))

    while True:
        n += 1
        if count_of_one == count_one(number_to_binary(n)):
            return n

bin 함수와 count 메서드를 사용하지 않을 경우 다음과 같은 함수를 만들어 사용할 수 있다.