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

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

코딩테스트 연습 - 다음 큰 숫자

자연수 n을 2진수로 바꾼 후, 1의 개수를 똑같이 해서 다음으로 큰 2진수를 구하는 문제입니다.

 

가장 마지막 자리가 1인 경우와 2인 경우로 나눌 수 있습니다.

 

가장 마지막 자리가 1인 경우, 0이 나올때까지 탐색해서 0을 1로 바꾸고 그 전 자리를 0으로 바꾸면 그 다음 수 입니다.

 

만약 1로만 이루어진 경우, 한자리를 추가하고 그 전 자리를 0으로 변경합니다.

 

가장 마지막 자리가 0인 경우, 연속되는 1의 개수를 체크합니다. 그 이후 0이 나온다면, 그 자리를 1로 바꿉니다.

 

그 후 뒤에서부터 1의 개수 만큼 1을 채우고, 나머지를 0으로 변경합니다.

 

연속되는 1로 끝나는 경우 맨 앞자리를 추가하고 변경합니다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> binary;     // 2진수를 담을 배열
    int a;                  // 나머지를 계산할 변수
    while(n>0)
    {
        a = n % 2;
        binary.push_back(a);
        n = n / 2;
    }
    
    bool find = false;
    bool findOne = false;
    int oneCount = 0;
    int index;
    
    if(binary[0] == 1)      // 맨 뒤가 1인 경우
    {
        for(int i = 0; i<binary.size();i++)
        {
            if(binary[i] == 0)  // 0이 나오는 순간 1로 바꾸고 그 전번을 0으로 변경하면 됨
            {
                find = true;
                binary[i] = 1;
                binary[i-1] = 0;
                break;
            }
        }
        
        if(find == false)       // 1로만 이루어진경우 맨 앞자리를 0으로 바꾸고 한자리를 추가함
        {
            binary[binary.size()-1] = 0;
            binary.push_back(1);
        }
    }
    
    else if(binary[0] == 0)     // 0인 경우
    {
        for(int k=0; k<binary.size(); k++)
        {
            if(binary[k] == 1)  // 연속되는 1의 개수 체크
            {
                oneCount++;
                findOne = true;
            }
            else if(binary[k] == 0 && findOne == true)  // 1이 나왔다가 0이 나오는경우
            {
                binary[k] = 1;
                oneCount--;
                index = k;
                find = true;
                break;
            }
        }
        
        if(find == true)    // 1이 나왔다가 0이 나오는 경우
        {
            for(int m=0; m<index; m++)
            {
                if(oneCount > 0)
                {
                    binary[m] = 1;
                    oneCount--;
                }
                else
                {
                    binary[m] = 0;
                }
            }
        }
        else if(find == false)  // 1이 연속됨
        {
            binary.push_back(1);
            oneCount--;
            
            for(int l=0; l<binary.size()-1; l++)
            {
                if(oneCount > 0)
                {
                    binary[l] = 1;
                    oneCount--;
                }
                else
                {
                    binary[l] = 0;
                }
            }
        }
    }
    
    int two = 1;

    for(int j=0; j<binary.size(); j++)
    {
        answer += binary[j] * two;
        two = two * 2;
    }       // 2진수 계산
        
    return answer;
}