[알고리즘C++] 다음 큰 숫자

오늘의 문제

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

다음 큰 숫자

나의 풀이

#include <string>
#include <vector>

using namespace std;

int cal(vector<int> bin){
    int res =0 ;
    int mul = 1;
    for(int i=0;i<bin.size();i++){
        res += bin[i]*mul;
        mul *= 2;
    }
    return res;
}

int solution(int n) {
    vector<int> binaryN;
    while(n != 0){
        binaryN.push_back(n % 2);
        n /= 2;
    }
    binaryN.push_back(0);
    int one=0;
    for(int i=0;i<binaryN.size();i++){
        if(binaryN[i] == 1){
            if(binaryN[i+1] == 0){
                binaryN[i] = 0;
                binaryN[i+1] = 1;
                for(int j=0;j<one;j++){
                    binaryN[j] = 1;
                }
                return cal(binaryN);
            }else{
                one++;
                binaryN[i] = 0;
            }
        }
    }
}

모범 답안

#include<iostream>
using namespace std;

int nextBigNumber(int n)
{
    int answer = 0;
    int ac = 0, k = n;
    while (k != 0) {
        ac += k % 2;
        k /= 2;
    }
    for (int i = n + 1;; i++) {
        int count = 0;
        k = i;
        while (k != 0) {
            count += k % 2;
            k /= 2;
        }
        if (count == ac) {
            answer = i;
            break;
        }
    }
    return answer;
}
int main()
{
    int n = 78;

    //아래는 테스트 출력을 위한 코드입니다.
    cout << nextBigNumber(n);
}

배울 점

• 규칙성을 찾고 정리한 후 문제를 풀게 되니 정확한 풀이가 가능했다.
• 규칙성이 있을 법한 문제는 이렇게 풀어야겠다