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

 이 문제는 구현 문제인 것 같다. 처음에는 입력 숫자의 최대 크기가 1,000,000 이고, 이에 대한 이진수는 1111 0100 0010 0100 0000 이고, 다음 큰 수는 대략 1111 0100 0010 1000 0000 으로 1,000,064가 되어 최대 시간 복잡도가 2^20 * 20 = 약 1억이라고 생각해 완전 탐색으로 구현하려고 했다. 그러나 생각을 더 해보면 n + 1 부터 시작해서 1의 개수가 같은 이진수가 나오는 숫자까지 반복하면 훨씬 짧은 수의 반복문으로 해결할 수 있을 것 같았다. 다음 큰 숫자가 생각보다 멀리 있지 않다는 점을 이용해서 풀었고, 정답을 맞출 수 있었다.

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string toBinary(int n) {
    string result = "";
    
    while (n > 0) {
        result += to_string(n % 2);
        n /= 2;
    }
    
    reverse(result.begin(), result.end());
    
    return result;
}

int solution(int n) {
    int answer = 0;
    
    // 초기화
    string binaryN = toBinary(n);
    int cntOne = 0;
    
    for (char c : binaryN) {
        if (c == '1') {
            cntOne++;
        }
    }
    
    int temp = n;
    while (true) {
        temp++;
        int cnt = 0;
        
        string tempResult = toBinary(temp);
        
        for (char c : tempResult) {
            if (c == '1') {
                cnt++;
            }
        }
        
        if (cnt == cntOne) {
            answer = temp;
            break;
        }
    }
    
    return answer;
}