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

https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

풀이

아래 블로그를 참고하여 구현하였습니다.

https://ye0nn.tistory.com/28

[프로그래머스] Level 2 - 2개 이하로 다른 비트 (Python)

짝수인 경우 마지막 비트가 항상 0이기 때문에 0을 1로 바꾸면, 조건을 만족하게되는 숫자입니다. 따라서 현재 숫자+1을 push_back합니다.

홀수인 경우 가장 앞쪽에 등장한 0을 1로 바꾸고 그 바로 앞 비트를 0으로 바꿔주면 됩니다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for (auto i : numbers) {
        // 짝수인경우 +1 이 정답
        if (i % 2 == 0)
            answer.push_back(i+1);
        else {
            /*
                홀수인 경우 가장 뒤쪽 0을 1로 바꾼 후 그 다음 비트를 0으로 바꿈
                reverse -> 0111 -> rfind('0') -> 1011 
            */
            string s;
            while (true) {
                if (i == 0)
                    break;
                s += to_string(i%2);
                i = i/2;
            }
            reverse(s.begin(), s.end());
            string new_s = "0" + s;
            long long idx = new_s.rfind('0');
            new_s[idx] = '1';
            new_s[idx+1] = '0';
            long long num = 0;
            for (int j = new_s.size()-1; j>=0; j--) {
                num += (new_s[j] - 48) * pow(2, new_s.size()-(j+1));
            }
            answer.push_back(num);
            // cout << new_s << " " << num << endl;
        }          
    }
    return answer;
}