Programmers - 다음 큰 숫자[파이썬(python)]

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12911

코딩테스트 연습 - 다음 큰 숫자

문제 설명

자연수 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. 주어진 수를 2진 수로 변환한다.
2. 연속으로 1이 등장하다 최초로 0이 등장하는 지점을 찾는다. (1이 한 번만 등장해도 상관없다.)
3. 연속으로 등장한 1이 후 처음 등장한 0을 1로 바꿔 주어진 수보다 큰 수를 만든다.
4. (연속한 1의 개수 -1) 개만큼 첫 번째 비트부터 1을 채우고 이후 처음 등장한 0의 위치까지는 0을 채운다.(조건에서 제시하는 2진수로 변환하였을 때 1의 개수가 같고 큰 수중 가장 작은 수를 만들기 위함)
5. 이후 비트는 주어진 수와 동일한 비트로 채워 조건에 만족하는 2진수를 생성한다.
6. 생성된 2진수를 10진수로 변환한다.

이해를 돕기 위해 n=78인 경우를 적용하여 위의 규칙을 따라가 보자.

step 1. 먼저 78을 2진수로 변환하면 1001110이다.

step 2. 연속으로 1이 등장하다 최초로 0이 등장하는 지점은 5번째 비트(1001110)이다.

step 3. 5번째 비트를 0에서 1로 변환하여 n보다 큰 수를 만든다. (1011110)

step 4. 연속한 1의 개수(1001110) 3-1인 2개만큼 첫 번째 비트부터 1을 채우고 이후 처음 등장한 0의 위치인 5번째 비트 까지는 0을 채운다. (1010011)

step 5. 이후 비트는 주어진 수와 동일한 비트로 채운다. (1010011)

step 6. 생성된 2진수 1010011을 10진수로 변환하여 답을 구한다.

 

구현 코드

코드 링크 : 다음 큰 숫자

def int_to_binary(num):
    arr = []
    while True:
        if num < 2:
            arr.append(num)
            break
        mode = num%2
        arr.append(mode) 
        num = int(num/2)
    arr.append(0)
    return arr

def solution(n):
    answer = 0
    bi = int_to_binary(n)
    current_bit = bi[0]
    count = 0
    for i, b in enumerate(bi[1:]):
        next_bit = b
        if current_bit == 1 and next_bit == 0:
            break
        elif current_bit == 1 and next_bit == 1:
            current_bit = next_bit
            count += 1
        else:
            current_bit = next_bit
            
    bi[i+1] = 1
    for j, b in enumerate(bi):
        if j < count:
            answer += 1*2**j
        elif count <= j <= i:
            continue
        else:
            answer += b*2**j
        
    return answer