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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

자연수 x에 대하여 x보다 큰 수 중 2진수 비트가 1~2개만 다른 가장 작은 수를 구하는 문제이다.

 

규칙을 찾아보면,

1) 000...1000 과 같이 가장 마지막 자리가 0인 경우 이를 1로 바꾸면 된다.

2) 000...0111 과 같이 마지막 자리가 아닌 자리가 0인 경우, 가장 뒷자리 부터 0을 찾아 이를 1로 바꾸고 해당 자리의 다음자리를 0으로 바꾼다. 예를 들어, 000...0111 을 바꾸면 1011이 되고, 10진수 7에 대한 정답은 11이 된다.

 

10진수를 2진수 문자열로 바꾸어 연산할 수도 있지만, 비트 연산을 이용하여 간단히 구현할 수 있다.

가장 끝 0번 인덱스부터 각 자리를 추출하여 해당 자리가 0이면 이를 1로 바꾸고, 0인 인덱스가 가장 끝 인덱스가 아닌 경우, 해당 자리의 뒷자리를 0으로 바꾼다.

모든 숫자에 대한 답을 계산하여 벡터를 리턴하면 정답이다.

 

 

참고하면 좋은 것

10진수 x가 있을 때, i번째 인덱스를 추출하는 연산은 x&(1<<i) 
i번째 인덱스를 1로 바꾸는 연산은 x|(1<<i)
i번째 인덱스를 0으로 바꾸는 연산은 x&(~(1<<i)) 

참고하면 좋은 포스트: (비트 연산_AND 연산/OR 연산/ XOR 연산/ NOT 연산 / Shift 연산 / 비트의 특정 인덱스 추출(업데이트) 참조)

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<long long> solution(vector<long long> numbers) {
    
    vector<long long> v;
    
    for (long long x : numbers) {
        for (int i=0; i<=50; i++) {
            int d = ((x&(1LL<<i)) > 0);
            if (d == 1) continue;
            x = x|(1LL<<i);
            if (i > 0) x = x&(~(1LL<<(i-1)));
            break;
        }
        v.push_back(x);
    }
    return v;
}