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

1.문제 링크

2개 이하로 다른 비트

2. 풀이 전 계획과 생각

• 규칙찾기

3. 풀이

#include <string>
#include <vector>

using namespace std;

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 bit = 1;
            while(true){
                if((numbers[i]&bit)==0) break;
                bit = bit*2;
            }
            answer.push_back(numbers[i]+bit/2);
        }
    }
    return answer;
}

짝수일 경우 +1, 홀수일 경우 가장 처음에 나오는 0을 1로, 그다음 비트를 0으로 만든다.

짝수의 경우에 비트로 보면 XXX0일 수밖에 없다. 만약 XXX1이라면 1이 추가되므로 무조건 홀수가 되기때문이다. 따라서 짝수 비트 XXX0에 1을 더하게되면 특정 짝수값보다 크고 비트가 1개 다른수들 중 가장 작은 수가 된다.

홀수의 경우 f(7) = 11이다. 여기서 보면 7(0111), 11(1011)로 다른 홀수 값에 대해서도 규칙이 발생한다.

4. 풀이하면서 고민했던 점

• 연산자 우선순위 고려 if(numbers[i]&bit==0) break; 이렇게 작성했더니 오류가 났다. 알고보니 연산자 우선순위 때문에 if((numbers[i]&bit)==0) break; 이런식으로 비트연산에 대해 괄호 처리를 해야한다.

5. 문제를 풀고 알게된 개념 및 소감

• 비트 연산을 복습하게됨.