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

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/77885

문제

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 10의 15제곱

풀이 과정

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

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

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

#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;
}

#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;
}