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

참고자료
해당 문제는 구글링을 통해 해결하였기 때문에 참고한 블로그를 상단에 첨부한다.
https://ansohxxn.github.io/programmers/148/#%EA%B7%9C%EC%B9%99-%EC%B0%BE%EA%B8%B0-2%EF%B8%8F%E2%83%A3-%ED%99%80%EC%88%98
https://ongveloper.tistory.com/59

📌2개 이하로 다른 비트

/*문제 설명은 생략*/

📌풀이

조건

1. x보다 커야한다.
2. x와 비트가 1~2개 다른 수들 중에서 제일 작은 수여야 한다.

이 두 조건을 만족하기 위해선 먼저 주어진 수들의 규칙을 찾아야한다.

2(10) -> 0010(2)
3(10) -> 0011(2)
4(10) -> 0100(2)
5(10) -> 0101(2)
6(10) -> 0110(2)
7(10) -> 0111(2)
8(10) -> 1000(2)
9(10) -> 1001(2)
10(10) -> 1010(2)
11(10) -> 1011(2)
...

위 수를 보면 짝수의 경우 최하위 비트가 0으로 끝나고, 홀수의 경우 최하위 비트가 1로 끝나는 것을 알 수 있다.

짝수의 경우,
예를 들어 2를 기준으로 설명할 때, 2보다는 크면서 0010과 비트가 다른 것 중 가장 작은 수는 3이 된다.
이 말은 곧 짝수는 그냥 +1 해준 값을 answer에 넣어주면 된다는 의미이다.
홀수의 경우,
예를 들어 3을 기준으로 설명할 때, 3보다 크면서 0011과 비트가 다른 것 중 가장 작은 수는 5가 된다.
5(0101)은 3(0011)과 비트가 다른 지점이 2개 이하면서 3보다는 크고 제일 작은 수이기 때문이다.
홀수에 대한 코드 구현이 다소 어려운데 다음과 같이 생각할 수 있다.

//홀수라면, 최하위 비트가 1
long long bit = 1;
   while (true){ //차례로 연속된 1 로 이루어진 비트구한다.
     if ((numbers[i] & bit) == 0) break;
     bit *= 2; // 곱하기 2 를 하면 다음 비트로 이동
   }
   bit /= 2;
   answer.push_back(numbers[i] + bit); // 구한 비트 더해주기
 }

연속된 1 비트의 개수가 n 개라고 할 때, n - 1 자리의 비트 수만큼 더해진게 우리가 구하자고자 하는 값(비트가 다른 것 중 가장 작은 수)이 된다고 할 수 있다.
ex. 101111 의 f 값은 000111 를 더한 값이 된다는 것이다.

이 코드의 풀이 역시 bit연산(&)을 이용하였고, 2진수의 비트 성질을 (2배씩 커지는) 이용하였다.

📌코드

#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) //짝수라면, 최하위 비트가 0
            answer.push_back(numbers[i] + 1);
        else
        { //홀수라면, 최하위 비트가 1
            long long bit = 1;
            while (true)
            {
                if ((numbers[i] & bit) == 0)
                    break;
                bit *= 2;
            }
            bit /= 2;
            answer.push_back(numbers[i] + bit);
        }
    }
    return answer;
}

더 나은 대안 (비트연산만 이용)

#include <vector>
using namespace std;
vector<long long> solution(vector<long long> numbers)
{
    vector<long long> answer;
    for (long long number : numbers)
    {
        long long bit = 1;
        while ((number & bit) > 0)
            bit <<= 1;
        answer.push_back(number + bit - (bit >> 1));
    }
    return answer;
}

다른 사람의 풀이 방법이다. 이 방법이 가장 깔끔하다고 생각된다.
먼저 for문을 돌면서 탐색하는 것은 동일하다.
*&연산을 이용하면 연산하려는 두 비트가 모두 1인 경우에만 1이 나온다. *

이를 이용하여 0이 나올 때까지 bit와 numbers & 연산하여 while문을 통해 bit를 왼쪽으로 시프트해주며 0이상이 될 때까지 bit값을 변경한다.

그렇게 해서 0이 되면 bit값이 변경되어 number와 연산한 결과가 곧 짝수가 되었다는 의미이고, answer에 number + bit - (bit >> 1)하여 값을 넣어준다.

1. 짝수라면 bit는 1이므로 number & bit 한 값이 0이 되어 while문에 들어가지 않고, 1 >> 1은 0이므로 number + 1한 값만 들어간다.
2. 홀수라면 number & bit 한 값이 1 이상이 되고, 최하위 비트가 0이 될 때까지 while문 안에서 bit << 해준다. 이후 while문에서 나온 다음 number + bit 해주고 (bit >> 1)한 값을 빼준다.

---

회고

개인적으로 프로그래머스에 월간 코드 챌린지에 대한 문제들은 좋은 문제라고 생각한다.
기본적인 것부터 심화적인 문제까지 다양하게 다룬다고 생각되기 때문이다.
비트연산 문제는 항상 어떻게 접근해서 풀어내야 할지가 관건인 것 같다.
또 풀어보아야징. 내 것이 될 때까지 ....