FrontEnd
Javascript
Diary
ML
CS
Django
Algorithm
AWS
Co-Work
HTML
CSS
Python
React
ReactNative

#36 알고리즘 연습 - 다음 큰 숫자(이진수 변환)(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 이하의 자연수 입니다.

입출력 예

n result
78 83
15 23

입출력 예 설명

입출력 예#1 문제 예시와 같습니다.

입출력 예#2 15(1111)의 다음 큰 숫자는 23(10111)입니다.

문제풀이
일단 주어진 숫자의 이진수 표현을 기준으로 동일 한 1의 갯수를 가지고 다음으로 큰 숫자를 찾는게 포인트였다.
그래서 규칙이 있는지 숫자들을 보았지만 10진수 표현에서는 규칙을 찾지 못했다..
그래서 이진수 변환 => 같은 1의 갯수를 기준으로 다음 큰수 찾기 => 다시 십진수변환
위의 과정을 python에서 제공하는 함수없이 구현해보았다.

내 풀이 🏆

def solution(n):
    cnt_pow = 0 #n을 2진수로 표현하기 위해 2의 몇 power인지 찾아내기 위한 변수(이진수 자리 관련)

    n2 = n #n을 n2에 복사해서 차수를 찾기 위해 사용한다
    t_digit = "" #이진수를 str의 형태로 만들어 준다

    answer = 0

    ########이진수 변환 과정 ################

    while n2 > 0:  #예를 들어 5라면  5//2 == 2  ->  2 //2 == 1  --> 1//2 == 0 0
        n2 = n2//2   #n2>1이 아니라 0으로 잡아준 이유는 5의 경우 101 이라는 이진수로 표현되기 때문에
        cnt_pow += 1  #이진수의 자릿수 만큼 cnt_pow를 설정해주기 위해서다
    for i in range(cnt_pow,0, -1): #이진수의 특징을 보면 2^3 | 2^2 | 2^1 | 2^0 이런식으로 자리구성이 구성이 되어 있으므로 역순으로 for문을 돌려 준다.  

        if n >= 2**(i-1): #대신 이진수의 자리수가 4라도 3~0 차수를 써야하므로 (i-1)을 해주고

            t_digit += "1"  #입력 받은 n이라는 값이  2**(i-1) 보다 크면 이진수에 1을 추가해주고

        else:
            t_digit += "0"
        n = n%2**(i-1)  #그리고 공통적으로 n값을  2**(i-1)로 나눈나머지를 n으로 저장해준다.

###############이진수의 (1의 갯수가 같으면서)다음으로 큰수 찾는 과정##############

    t_digit = [int(i) for i in t_digit] #list comprehension으로 문자를 숫자로 바꾸어 다음으로 큰수를 찾기위한 이진수 list를 만들어 준다.

    t_digit2 = [int(i) for i in t_digit] #다른 방법으로도 할수 있겠지만 간단하게 기존의 1의 갯수가 몇개인지 기준점이 되는 이진수도 list로 저장해 놓는다. (빠르기는 문자열에서 찾는게 더 빠르다)




    while True:
        t_digit[-1] += 1 #list의 끝자리 즉 이진수에 1을 더한다
        for i in range(1,len(t_digit)+1): # for 문을 이용해서 list의 끝자리 부터 이진수 연산을 차례대로 수행해준다.


            if i == len(t_digit):  #만약 맨 앞자리까지 for문이 돌았다면 맨 앞자리가 2가 되었다는 의미이므로

                t_digit[-i] = 0 #맨 앞자리를 0 으로 바꿔준다음 


                t_digit = [1]+t_digit #리스트의 앞부분에 1을 추가해줘 이진수의 자릿수를 늘려준다

            if t_digit[-i] == 2: #이진수의 연산중에 2가 생성되면


                t_digit[-i]=0  #해당 자리를 0 으로 만든다음 상위 자리에 1을 더해주는 연산을 한다

                t_digit[-i-1]+=1
            if t_digit[-i] == 1: #만약 1을 더했는데 자리에 1이 와있다면 for문이 돌아갈 필요없이 종료된다.

                break
        if t_digit.count(1) == t_digit2.count(1):  #그리고 while문은 계속 1을 더해가면서 연산하는 list와 기준점 list의 1이 같으면 탈출한다


            break

###########10 진수 변환 과정 ################

    for i in range(len(t_digit)):
        answer += t_digit[i]*(2**(len(t_digit)-1-i))  #만들어진 이진수를 이용해 각 자리에 맞는 2의 power형태로 answer에 더해준다.




    return answer

마음이 편해지는 bin 풀이 🏆

def nextBigNumber(n):


    num1 = bin(n).count('1')    #n을 bin함수를 이용해 바꿔준후 count를 이용해 1의 갯수를 찾아준다.
    while True:         
        n = n + 1               #입력받은 n에서 1을 더해가며
        if num1 == bin(n).count('1'):   #1을 더한 값을 다시 이진수로 바꾸어 count로 1의 갯수를 찾아
            break                       #기준이랑 일치하면 break해준
    return n