[77885] 2개 이하로 다른 비트(C++)

 

문제

프로그래머스

 

 

해결 방법

f(1), f(2), f(3)... 이렇게 하나씩 구하다보면 규칙을 찾을 수 있는 문제

우선 x가 짝수인 경우 f(x)는 항상 x + 1이다.

그 이유는 x가 짝수이기 때문에 가장 마지막 비트가 0이고 따라서 이 자리만 1로 바꿔주면 f(x)가 되기 떄문이다.

 

x가 홀수인 경우에도 규칙이 있다.

제일 낮은 자리의 비트부터 앞으로 탐색하면서 가장 처음으로 0이 나타나는 위치를 먼저 구하고,

이 위치는 1로 바꾸고 바로 오른쪽의 비트는 0으로 바꾸면 된다.

 

예를 들어,

x = 7 = 111(2)인 경우는 가장 처음으로 0이 나타나는 위치가 2^3 자리이다. 

따라서 이 자리를 1로 바꾸면 1111이 되고, 바로 오른쪽의 비트를 0으로 바꾸면 1011, 즉 f(7)이 완성된다.

 

이제 이것을 어떻게 구현하느냐가 관건인데,

사실 이 문제는 비트 연산을 사용하면 엄청 짧고 간단하게 풀 수 있지만 비트를 문자열로 보고 구현해도 통과가 되긴 한다.(거의 1초에 가까운 시간이 걸리긴한다)

비트 연산을 사용하고자 한다면 홀수인 경우를 어떻게 처리해야할지가 좀 헷갈릴 수 있는데,

가장 낮은 자리부터 탐색을 하면서 제일 처음으로 0이 나오는 자리를 찾는다.  그럼 이 뒤의 비트는 전부 1이었다는 소리.

 

예를 들어, f(11)을 구하려 한다면 11 = 1011(2)이고 f(11) = 1101(2) = 13이 될 것이다. 

1011(2) -> 1101(2) 이 되려면 1011에 10을 더해줘야 한다. 그래야 2^2자리의 1이 0으로 변하고 2^3자리의 0이 1로 변할 수 있기 때문

 

다른 예시로, f(23)을 구하려 한다면 23 = 10111(2)이고 f(23) = 11011(2) = 27이 될 것이다.

여기서도 10111(2) -> 11011(2)가 되기 위해 10111에 100을 더해주면 된다.

 

즉, 가장 낮은 비트부터 탐색하면서 만약 i번째 비트가 0이라면 x에 2^(i-1)을 더한값이 f(x)가 되는 것!

 

 

내 코드

1) 비트 연산 사용 X(오래 걸림, 비추👎)

// [77885] 2개 이하로 다른 비트
#include <string>
#include <vector>
#include <cmath>
using namespace std;

vector<int> binary;

void getBinaryNum(long long x)
{
    binary.clear();
    while(x > 0) {
        binary.push_back(x % 2);
        x /= 2;
    }
}

void fx()
{
    for(int i = 0; i < binary.size(); i++) {
        if(binary[i] == 0) {
            binary[i] = 1;
            if(i-1 >= 0 && binary[i-1] == 1) {
                binary[i-1] = 0;
            }
            return;
        }
    }
    // x의 모든 비트가 1인 경우
    binary.push_back(1);
    binary[binary.size() - 2] = 0;
}

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(int i = 0; i < numbers.size(); i++) {
        getBinaryNum(numbers[i]);
        fx();
        int idx = 0;
        long long result = 0;
        for(int i = 0; i < binary.size(); i++) {
            result += pow(2, idx) * binary[i];
            idx++;
        }
        answer.push_back(result);
    }
    return answer;
}

 

2) 비트 연산 사용(추천👍)

// [77885] 2개 이하로 다른 비트
#include <string>
#include <vector>
using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(long long num : numbers) {
        if(num % 2 == 0) answer.push_back(num + 1);
        else {
            long long bit = 1;
            while(true) {
                // 연산자 우선순위: == > & -> 반드시 괄호 필요
                if((num & bit) == 0)  break; 
                else bit <<= 1; // bit *= 2;
            }
            bit >>= 1; // bit /= 2
            answer.push_back(num + bit);
        }
    }
    return answer;
}