(Python) 프로그래머스 Lv2. 다음 큰 숫자

문제

자연수 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):
    binary = list('0' + format(n, 'b'))     # 2진수화 시킴(1만 있는 경우를 대비해 앞에 0 추가)
    start = -1
    end = -1
    for i in range(len(binary)-1, -1, -1):  # 뒤에서부터 거슬러서 처음 나오는 1 찾기
        if binary[i] == '1':
            start = i
            break
    
    for j in range(start-1, -1, -1):        # 앞서 찾은 처음 나오는 1 위치부터 시작해서, 처음 나오는 0 찾기
        if binary[j] == '0':                # 찾았을 경우, 앞에 나온 1과 위치 바꾸기
            binary[j] = '1'
            binary[start] = '0'
            end = j
            break
    
    etc = binary[end+1:]                    # 바꾼 위치보다 작은 자리를 자르기
    etc.sort()                              # 정렬해서, 가장 작은 값으로 만들기(1010 -> 0011)
    binary = binary[:end+1] + etc           # 새로운 정답 리스트 만들기
    answer = int(''.join(b for b in binary),2) # 문자열화 시킨 후 다시 10진수화
    return answer
    

• 문제를 풀기 위해 구상했던 생각

  이진수로 만든 뒤, 앞에 0을 추가한다. (1만 있는 경우를 방지 = 빈자리 만들기)
  규칙 1. n보다 큰 자연수여야 한다.
  규칙 2. 1의 갯수가 같아야 한다.
  이기 때문에, 1을 오른쪽에서 왼쪽으로 이동시켜야 한다.
  이동시킨 이후, 이동된 위치보다 낮은 자릿수의 숫자를 가장 낮게 만든다.
  규칙 상 0은 올 수 없다.
  ======= 풀이 ========
  가장 낮은 1을 찾는다.
  해당 위치로부터 왼쪽으로 이동하며 0을 찾는다.
  두 위치를 교환한다.
  교환된 위치로부터 아래를 정렬한다.