[알고리즘문제] 프로그래머스 - 다음 큰 숫자

처음이 문제를 n을 2진수로 표현했을 때 1을 더하는 문제인 줄 알았다. 그래서, 올림을 어떻게 구현할 것인가 하고 고민을 했는데,

예제를 보니 내가 잘못이해하고 있다는 것을 그때 알았다.

 

문제는n 숫자가 있을 때 n보다 크면서 2진수로 표현했을 때 1의 개수가 같은 숫자를 구하는 문제이다.

예를 들어 15의 경우 2진수로 표현하면 (1111), 1이 4개이고 15보다 큰 숫자중에 2진수로 표현했을 때 1의 개수가 4개인 숫자는 23(10111)이다. 이때 23을 return 하면 된다.

 

문제를 보자마자 시프트 연산과 비트연산자(&)를 사용했다.

n을 오른쪽으로 0,1,2,3,4....19씩 이동하면서 1과 논리연산자를 했을 때 1의 개수를 체크해준다. 

 

1001110

          1       -> 0

0100111

           1       -> +1

0010011

            1      -> +1

0001001

             1     -> +1

.........

 

위의 과정을 19번 반복하는데, 19인 이유는 문제에서 n의 최대값이 1,000,000이라고 했는데 이를 2진수로 표현하면 19자리수 이기 떄문이다.

 

이렇게 처음 n의 1의 개수를 확인하고, n+1~1,000,000에서 1의 개수가 n과 같은 첫번째 숫자를 return g하면 된다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n) {
 
    int count = 0;
    int z = n;
    
    // 시프트 연산으로 n에 1이 몇개 있는지 검사
    // i의 범위가 19인 이유는 n의 최대값이 1,000,000이며, 2진수로 표현하면 19자리이기 때문이다.
    // 연산자 우선순위는 '>>'이 '&'보다 높다
    for(int i=0;i<=19;i++){ 
        if(z >> i & 1){
            count++;
        }
    }
    
    for(int i=n+1;i<=1000000;i++){ 
        int c = 0;
        for(int k=0;k<=19;k++){ // n+1부터 돌면서 이진수로 표현했을 때, 1의 수가 같으면 해당 숫자를 return;
            if(i >> k & 1){
                c++;
            }
        }
        if(c == count){
            return i;
        }
    }
}