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

처음에 이진수의 모든 가능한 경우를 구한 후 다음 큰 숫자를 구하려고 했다.

하지만 효율성 문제를 해결하지 못했고 다른 방법을 이용해야 했다.

 

풀이:

현재 숫자에서 1을 증가시키고  이진수에서의 1의 개수를 카운트 한다.

주어진 숫자의 1의 개수와 증가시킨 숫자의 1의 개수가 같다면 그  때의 값이 답이다.

 

아래는 틀린 답

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<string> store;
 
void DFS(string str, int limit, int count, int subCount) {
    if (str.length() == limit || subCount > count) {
        if (count == subCount) {
            store.push_back(str);
        }
        return;
    }
    
    DFS(str + '0', limit, count, subCount);
    DFS(str + '1', limit, count, subCount + 1);
}
 
int solution(int n) {
    int answer = 0;
    
    store.clear();
    int N = n;
    string binary = ""; 
    while(N > 1) {
        if(N % 2 == 0) {
            binary += '0';
        } else {
            binary += '1';
        }
        N /= 2;
    }
    binary += '1';
    
    int count = 0;
    for(int idx = 0; idx < binary.length(); idx++) {
        if(binary[idx] == '1') { count++; }
    }
    
    DFS("", binary.length() + 1, count, 0);
    
    sort(store.begin(), store.end());
    
    for(int idx = 0; idx < store.size(); idx++) {
        int val = 0;
        int plus = 1;
        int subCount = 0;
        for(int i = store[idx].length() - 1; i >= 0; i--) {
            if(store[idx][i] == '1') {
                val += plus;
                subCount++;
            }
            plus *= 2;
        }
        if(val > n) {
            answer = val;
            break;
        }
    }
    
    return answer;
}

AC 받은 답

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int binaryCount(int N) {
    string binary = ""; 
    while(N > 1) {
        if(N % 2 == 0) {
            binary += '0';
        } else {
            binary += '1';
        }
        N /= 2;
    }
    binary += '1';
    
    int count = 0;
    for(int idx = 0; idx < binary.length(); idx++) {
        if(binary[idx] == '1') { count++; }
    }
    
    return count;
}
 
int solution(int n) {
    int answer = 0;
    
    int count = binaryCount(n++);
    while (count != binaryCount(n)) {
        n++;
    }
    
    answer = n;
    return answer;
}