프로그래머스 다음 큰 숫자

문제 바로가기

자연수 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 이하의 자연수 입니다.

접근방식

문제를 보자마자 두 가지 방식이 떠올랐다.

1. Bitset 사용하기
2. 비트연산자 사용하기

뭔가 2번 으로 풀고싶어졌다.

조건에서 규칙을 찾아보자.
78(1001110)의 다음 큰 숫자는 83(1010011)이다. 두 수를 보면 오른쪽에서 4~5번째 순서에서 규칙을 찾을 수 있다.
즉, 1 다음에 처음으로 0이 나왔을때 1과 0 두 수를 바꿔주고 나머지 오른쪽에 있는 1들은 제일 오른쪽으로 이동시켜주면 되는것이다.

4번째와 5번째 수를 변경 (1010110) -> 나머지 1들은 맨 오른쪽으로 이동 (1010011)

숫자 15로도 해보자.
15(1111)의 다음 큰 숫자는 23(10111)이다.

4번째와 5번째 수를 변경 (10111) -> 나머지 1들을 맨 오른쪽으로 이동 (10111)

뭔가 설명이 안 와닿을수도 있다. 일단 이런 알고리즘으로 작동한다는걸 이해하고 코드로 구현해보자.

#include <stack>
using namespace std;

int solution(int n) {
    int answer = n, num_of_one = 0,k = 1;
    stack<int> a; 
    if(n & 1 == 1) num_of_one++;
    a.push(n & 1);
    n >>= 1;
    while(1){ 
    //1. n을 1과 &연산을 해주고 나온 숫자를 a라는 스택에 넣어준다. 연산결과가 1인경우 count센다.
    //2. n을 1씩 오른쪽으로 비트 이동을 해준다.
    //3. 스택의 top이 1이고 n의 제일 오른쪽 비트가 0일 때 멈춰준다.
        if(n == 0) break;
        if(a.top() == 1 && (n & 1) == 0) break;
        else{
            if((n & 1) == 1) num_of_one++;
            a.push(n & 1);
            n >>= 1;
        }   
    }
    answer |= (k << a.size()); //1 바로 다음의 0을 1로 바꿔준다.
    for(int i = 0; i< a.size(); i++){
        if(i < num_of_one-1) answer |= k; 
        //1개수 하나 빼주고 아래 1들을 제일 오른쪽으로 이동
        else answer &= ~k;
        //나머지는 0으로 바꿔준다
        k <<= 1;
    }
    return answer;
}