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

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

프로그래머스

 

풀이과정

이 문제는 홀수인지, 짝수인지 구분해서 해결해야하는 문제이다.

짝수일 경우에는 비트의 끝자리가 항상 0이기 때문에 다음 숫자가 들어오면  
끝자리가 0에서 1로 바뀌게 된다. 그러므로 x보다 큰 값은 항상 현재값 + 1이 된다.

그러나, 홀수일 경우에는 비트의 끝자리가 항상 1이기 때문에 **올림수**가 발생하게 된다.  
1이 연속하는 수를 세어 3번 연속이라면 2의 2제곱, 4번 연속이라면 2의 3제곱 식으로 된다.  
즉, 연속된 1 비트의 개수가 n개라고 할 때, n - 1 자리의 비트 수만큼 더해진다.
(2자리의 비트수 = 4, 3자리의 비트수 = 8)

 

풀이 1

#include <string>
#include <vector>
#include <cmath>

using namespace std;

string binary(long long num){
    string str = "";
    while(num != 0){
        str += to_string(num % 2);
        num /= 2;
    }
    return str;
}
vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(int i = 0; i < numbers.size(); i++){
        if(numbers[i] % 2 == 0) answer.push_back(numbers[i] + 1);
        else{
            long long cnt = 0;
            string str = binary(numbers[i]);
            for(int j = 0; j < str.size(); j++){
                if(str[j] == '1') cnt++;
                else break;
            }
            answer.push_back(numbers[i] + pow(2, cnt - 1));
        }
    }
    return answer;
}

 

풀이 2

#include <string>
#include <vector>

using namespace std;
// pow 함수 구현
long long pow(long long a, long long b){
    if(b == 0) return 1;
    else if(b == 1) return a;
    else return a * pow(a, b - 1);
}

string binary(long long num){
    string str = "";
    while(num != 0){
        str += to_string(num % 2);
        num /= 2;
    }
    return str;
}

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(int i = 0; i < numbers.size(); i++){
        if(numbers[i] % 2 == 0) answer.push_back(numbers[i] + 1);
        else{
            long long cnt = 0;
            string str = binary(numbers[i]);
            for(int j = 0; j < str.size(); j++){
                if(str[j] == '1') cnt++;
                else break;
            }
            answer.push_back(numbers[i] + pow(2, cnt - 1));
        }
    }
    return answer;
}