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

---

🔗 문제 링크

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

프로그래머스

---

728x90

반응형

👩‍💻 코드

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for (auto number : numbers) {
        if (number % 2 == 0) {
            answer.push_back(number + 1);
        } else {
            long long mask = 1LL;
            while (number & mask) {
                mask <<= 1;
            }
            
            answer.push_back(number + mask - (mask >> 1));
        }
    }
    
    return answer;
}

---

📝 풀이

x가 짝수인 경우 비트의 마지막 0을 1로 바꾸면 x보다 크고 비트가 1개만 다르기 때문에 1을 더해줍니다.

 

홀수인 경우 가장 오른쪽의 0을 1로 바꾸고, 그 다음 위치의 1을 0으로 바꾼 수가 f(x)가 됩니다.

mask가 number의 비트에서 0을 만날 때까지 이동하여 가장 오른쪽에 있는 0을 찾습니다.

가장 오른쪽에 있는 0을 찾으면 1로 바꾸어 줍니다. 👉 mask <<= 1;

 

mask가 가리키는 위치를 1로 바꾸고 👉 number + mask

mask를 오른쪽으로 한 비트 이동시켜 그 다음 위치를 가리킵니다.

그 다음 위치는 0으로 바꾼 후 계산합니다.

 

최종적으로 answer을 return 합니다.