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

규칙 찾기 1️⃣ 짝수

• 2,4,6,.. 짝수들은 비트로 표현했을 때, 가장 오른쪽 비트는 항상 0 이다. 가장 오른쪽 비트는 \(2^0 = 1\) 에 대응하며, 그외 나머지 비트들은 모두 \(2^i\) 으로 짝수이기 때문이다. 가장 오른쪽 비트가 1 이면 + 1이 된다는 것이므로 그 비트는 무조건 홀수가 될 수 밖에 없다.
• 따라서 짝수인 수 2n 들의 f 값은 언제나 2n + 1 이다. 1 만큼 더한 다음 홀수! 짝수들은 가장 오른쪽 비트가 0 이기 때문에 1 을 더해주면 별다른 ‘올림’ 없이 이 가장 오른쪽 비트만 1 로 바뀌게 되기 때문에 비트가 총 1 개 다르게 된다.

        if (numbers[i] % 2 == 0)
            answer.push_back(numbers[i] + 1);

규칙 찾기 2️⃣ 홀수

• 홀수를 비트로 표현하면 가장 오른쪽 비트가 무조건 1 이다!
  • 그렇기 떄문에 홀수는 더했을 때의 ‘올림’을 생각해야 한다.
    • 1 만 더해주어도 올림이 되어 “최소 2 개의 비트”가 달라지기 때문이다. 가장 오른쪽 비트는 0 이 되며 올림을 통해 왼쪽 비트들의 수가 바뀌기 때문에 그렇다. 01 👉 10
• 홀수는 오른쪽에서부터 연속된 1 의 비트의 개수가 f 값과 연관이 있다.
  • 101111 이렇게 연속된 4 개의 1 비트를 가진 수의 f 값을 찾고자 한다면, 101111 👉 110111 이 되어야 한다. (후자가 f 값)
  • 즉! 연속된 1 비트의 개수가 n 개라고 할 때, n - 1 자리의 비트 수만큼 더해진게 f 값이 된다고 할 수 있겠다. 101111 의 f 값은 000111 를 더한 값이 된다는 것이다.

        else {
            long long bit = 1;
            // 가장 오른쪽부터 차례로 n 개의 연속된 1 로 이루어진 비트구하기
            while (true) {
                if ((numbers[i] & bit) == 0) break;
                bit *= 2; // 곱하기 2 를 하면 다음 비트로
            }
            bit = bit / 2;

            // 구한 비트 더해주기
            answer.push_back(numbers[i] + bit);
        }

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기