[프로그래머스] 다음 큰 숫자

문제

다음 큰 숫자

https://school.programmers.co.kr/learn/courses/30/lessons/12911

 

 

예시 코드

def solution(n):
    x = n
    # 1. 가장 낮은 '1'비트 찾기
    right_one = x & -x
    # 2. 가장 낮은 '1'비트에 1 더하기
    added_one_bit = x + right_one
    # 3. 변경된 비트 패턴 찾기
    modified_pattern = x ^ added_one_bit
    # 4. 변경된 비트 패턴 조정하기
    # 4-1. 오른쪽 끝으로 시프트하기
    adjusted_pattern = (modified_pattern) // right_one 
    # 4-2. 오른쪽으로 2비트 시프트하기
    adjusted_pattern >>= 2
    # 5. 최종 결과 구하기
    next_n = added_one_bit | adjusted_pattern
    
    return next_n

 

풀이

자연수 n의 다음 큰 수를 찾는 조건은 다음과 같습니다.

1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

이를 위해 비트 연산을 사용합니다.

 

로직은 다음과 같습니다.

1. 가장 낮은 '1'비트 찾기
   컴퓨터는 음수를 표현할 때, 보통 '2의 보수'라는 방식을 사용합니다. -x는 x의 모든 비트를 반전시키고 1을 더한 값입니다. 따라서, x와 -x를 AND 연산하면, x의 가장 낮은 '1'비트만 남게 됩니다.
2. 가장 낮은 '1'비트에 1 더하기
   x의 가장 낮은 '1'비트에 1을 더합니다.
3. 변경된 비트 패턴 찾기
   x와 2번의 결과값(added_one_bit)을 XOR 연산하면, 변경된 비트 패턴을 얻을 수 있습니다. 원래 비트와 새로운 비트의 차이를 나타냅니다.
4. 변경된 비트 패턴 조정하기
   변경된 비트를 조정해 최소값을 만들어 원래 값 x에 더해주기 위함입니다.
   1. 오른쪽 끝으로 시프트하기
      3번의 결과값(modified_pattern)을 1번의 결과값(right_one)으로 나누어 오른쪽 끝으로 정렬합니다.
   2. 오른쪽으로 2비트 시프트하기
      4-1번 결과값을 오른쪽으로 2비트 시프트합니다. 가장 낮았던 '1'비트의 오른쪽 비트와 왼쪽 비트가 총 2비트 차이 나기 때문에 그만큼 시프트합니다.
5. 최종 결과 생성
   마지막으로, 2번의 결과값(added_one_bit)과 4번의 결과값(adjusted_pattern)을 OR 연산하여, 최종적으로 '1'의 개수가 같으면서 n보다 큰 가장 작은 수를 생성합니다.

 

예시를 보면서 과정을 따라가보겠습니다.

 

n = x = 12일 때

1. 가장 낮은 '1'비트 찾기
   right_one = x & -x
   1100 & 0100 = 0100
2. 가장 낮은 '1'비트에 1 더하기
   added_one_bit = x + right_one
   1100 + 0100 = 10000
3. 변경된 비트 패턴 찾기
   modified_pattern = x ^ added_one_bit
   1100 ^ 10000 = 11100
4. 변경된 비트 패턴 조정하기
   1. 오른쪽 끝으로 시프트하기
      adjusted_pattern = (modified_pattern) // right_one
      11100 // 00100 = 00111
   2. 오른쪽으로 2비트 시프트하기
      adjusted_pattern >>= 2
      00111 >> 2 = 00001
5. 최종 결과 구하기
   next_n = added_one_bit | adjusted_pattern
   10000 | 00001 = 10001

따라서 답은 17이 됩니다.