프로그래머스 2개 이하로 다른 비트 (C++)

프로그래머스

숫자X를 비트로 변환 했을 때, X보다 크고, 비트가 1~2개 다른 수들 중에서 제일 작은 수를 찾아주세요.

 

 

풀이 방법

X보다 크면서 비트가 1~2개 다른 수들 중 가장 작은 수를 찾는 방법은 3가지 있습니다.

 

1. 마지막 bit가 0인 경우

2. bit들 중에 0이 있는 경우

3. 모든 bit가 1로 되어있는 경우

 

1번의 경우이는 마지막 비트 0을 1로 바꿔주면 해결입니다.

10000 -> 10001

 

2번의 경우에는 가장 오른쪽에 있는 0을 1로 바꾸고 그 오른쪽에 있을 1을 0으로 바꿔주면 됩니다.

10001 -> 10010

 

3번의 경우에는 가장 왼쪽에 있는 1을 0으로 바꾸고 왼쪽에 1을 추가해주면 됩니다.

11111 -> 101111

모든 수를 위의 방식을 통해 찾아주면 됩니다.

 

 

정답 코드

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

using namespace std;

string itob(long long num)
{
    string ret = "";
    while (num > 0)
    {

        ret = to_string(num % 2) + ret;
        num /= 2;
    }
    
    return ret;
}

long long btoi(string num)
{
    long long ret = 0;
    
    for (int i = 0; i < num.size(); i++)
    {
        ret *= 2;
        ret += num[i] - '0';
    }
    return ret;
}

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for (auto num : numbers)
    {
        string bit = itob(num);       
        
        int idx = -1;
        for (int i = bit.size()-1; i >= 0; i--)
        {
            if (bit[i] == '0')
            {
                idx = i;
                break;                
            }
        }
        
        // bit중에 0이 있다면 가장 오른쪽의 0을 1로 바꾼 수 (1개 차이)
        if (idx != -1)
        {
            bit[idx] = '1';
            if (idx < bit.size()-1) // 만약 오른쪽에 수가 더 존재한다면 1을 0으로 바꿈
                bit[idx+1] = '0';
        }
        
        // bit중에 0이 없다면 가장 왼쪽의 0을 1로 바꾸고 그 다음 1을 0으로 바꿈 (2개 차이)
        else
        {
            bit[0] = '0';
            bit = "1" + bit;
        }
        answer.push_back(btoi(bit));
        
    }
    
    return answer;
}