[프로그래머스] 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 이하의 자연수 입니다.

 

입출력 예

입력	출력
78	83
15	23

 

해답 및 해설

파이썬 (Python)

비트 연산을 이용한 풀이

def solution(n):
    n_test = n
    is_1_appeared = False
    is_1_disappeared = False
    idx = 0
    frist_1_idx = 0
    last_1_idx = 0
    
    while n_test >= 0:
        if not is_1_appeared and 1 & n_test:
            first_1_idx = idx
            is_1_appeared = True
        elif is_1_appeared and not 1 & n_test:
            is_1_disappeared = True
            last_1_idx = idx-1
            break
        
        n_test >>= 1
        idx += 1
    
    n_delete1 = n & ~((1<<(last_1_idx+1))-1)
    
    answer = n_delete1 + (1<<(last_1_idx+1)) + (1<<(last_1_idx-first_1_idx)) - 1
    
    return answer

내 첫 풀이로, 아이디어는 우선 각 자리수를 계속 검사하여 연속하는 1이 나오는 자리수의 시작과 끝을 구해주었다. 그 후 가장 끝자리는 한 자리수를 더 올려주고, 나머지는 오른쪽으로 붙이는 방식으로 시행하였다. 구체적인 설명은 아래와 같다.

• n & ~((1<<(last_1_idx+1))-1) : 연속하는 1을 없앤 수
• (1<<(last_1_idx+1)) : 마지막 1은 한 자리를 더 올려줌
• (1<<(last_1_idx-first_1_idx)) - 1 : 나머지 1만큼 오른쪽 끝에 붙여줌

 

def solution(n):
    i, j = 1, 1    

    while not (n // i) % 2: i*=2

    n -= i
    i *= 2

    while (n // i) % 2:
        n += j - i
        j *= 2
        i *= 2

    return n+i

 다른 사람의 해법을 보던 도중 더 이진연산스러운 간단한 해법을 찾아내었다. 우선 처음 반복문으로 가장 이진법에서 오른쪽에 있는 1을 찾아낸다. 그리고 그 1을 지우고(1 갯수 하나 줄이기), 거기에다 2배를 해준다. 이후 반복문을 이용하여 나머지 1을 오른쪽으로 하나씩 옮겨준다. 계속 i-j를 빼줘서 옮겨준다는 생각은 어떻게 했는지 참 대단하다.

 아래에 각 과정마다 값의 변화를 나타낸 것이다.

단계	n	i	i-j
시작	10011100	1
첫번째 while 끝	10011100	100
n-=i, i*=2	10011000	1000
반복문 1st 반복	10010001	10000	111
반복문 2nd 반복	10000011	100000	1110
결과 n+i	10100011

 

문자열을 이용한 방법

def solution(n):
    num1 = bin(n).count('1')
    while True:
        n += 1
        if num1 == bin(n).count('1'):
            break
    return n

파이썬 기본 2진법 변환을 이용 1의 갯수를 세어준 뒤, 1씩 더하여 1의 갯수가 같아질 때까지 확인해주는 방법이다.