문제 링크

내 코드

Bit 이용 - 푸는데 좀 걸림.

3ms, 8.05MB

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int setBit = countSetBit(num2);

        vector<int> num1Bits(32, 0);
        int cnt{};
        while(num1) {
            if(num1 & 1) num1Bits[cnt] = 1;
            num1 >>= 1;
            cnt++;
        }
        
        int answer{};
        for (int i = cnt - 1; i >= 0; --i) {
			answer <<= 1;
			if (num1Bits[i] && setBit) {
				answer |= 1;
				--setBit;
			}
		}
        
        int b = 1;
        while(setBit) {
            if(!(answer & b)) {
                answer |= b;
                --setBit;
            }
            b <<= 1;
        }

        return answer;
    }

private:
    int countSetBit(int num) {
        int cnt{};
        while (num) {
			if (num & 1) ++cnt;
			num >>= 1;
		}
        return cnt;
    }
};

Solution

Approach 1: From Optimal to Valid

• 0ms, 7.78MB
• Complexity
  • Let $n$ be the maximum possible value of num1 or num2.
  • Time Complexity: $O(\log n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        // Initialize result to num1. We will modify result.
        int result = num1;

        int targetSetBitsCount = __builtin_popcount(num2);
        int setBitsCount = __builtin_popcount(result);

        // Start with the least significant bit (bit 0).
        int currentBit = 0;

        // Add bits to result if it has fewer set bits than the target.
        while (setBitsCount < targetSetBitsCount) {
            // If the current bit in result is not set (0), set it to 1.
            if (!isSet(result, currentBit)) {
                setBit(result, currentBit);
                setBitsCount++;
            }
            // Move to the next bit.
            currentBit++;
        }

        // Remove bits from result if it has more set bits than the target.
        while (setBitsCount > targetSetBitsCount) {
            // If the current bit in result is set (1), unset it (make it 0).
            if (isSet(result, currentBit)) {
                unsetBit(result, currentBit);
                setBitsCount--;
            }
            // Move to the next bit.
            currentBit++;
        }

        return result;
    }

private:
    // Helper function to check if the given bit position in x is set (1).
    bool isSet(int x, int bit) { return x & (1 << bit); }

    // Helper function to set the given bit position in x to 1.
    void setBit(int &x, int bit) { x |= (1 << bit); }

    // Helper function to unset the given bit position in x (set it to 0).
    void unsetBit(int &x, int bit) { x &= ~(1 << bit); }
};

GPT (o3-mini-high)

이 코드는 두 정수 num1과 num2가 주어졌을 때,
num1을 기반으로 하면서 num2와 같은 개수의 1비트(즉, set bit)를 갖도록 num1의 일부 비트를 조정하여
num1과의 XOR 값이 최소가 되는 수를 만드는 문제를 해결합니다.

즉,

• 목표: 결과 수(result)는 __builtin_popcount(num2) (즉, num2의 set bit 개수)와 같아야 하며,
• 결과 수(result)는 num1과 최대한 비슷해야 하므로, 작은 자리수(낮은 비트)부터 수정하여 XOR 차이를 최소화합니다.

아래 단계별로 코드의 동작을 살펴보겠습니다.

---

1. 초기화

int result = num1;
int targetSetBitsCount = __builtin_popcount(num2);
int setBitsCount = __builtin_popcount(result);

• result:
  초기 결과를 num1으로 설정하고, 여기에 bit 조작을 진행합니다.

• targetSetBitsCount:
  num2의 set bit 개수를 구합니다.
  결과 수는 이 값만큼 1비트를 가져야 합니다.

• setBitsCount:
  현재 result(즉, num1)의 set bit 개수를 구합니다.

---

2. set bit 개수가 목표보다 적은 경우 (추가 작업)

int currentBit = 0;
while (setBitsCount < targetSetBitsCount) {
    if (!isSet(result, currentBit)) {
        setBit(result, currentBit);
        setBitsCount++;
    }
    currentBit++;
}

• 목적:
  만약 num1에 있는 1비트의 개수가 target보다 적다면,
  결과에 추가 1비트를 낮은 자리부터 설정하여 num1과의 값 차이를 작게 유지합니다.

• 동작:

  • currentBit는 0 (최하위 비트)부터 시작하여,
  • result의 currentBit 자리가 0이면, 1로 설정합니다.
  • 매번 set bit를 추가할 때마다 setBitsCount를 1 증가시킵니다.
  • 이 과정을 targetSetBitsCount에 도달할 때까지 반복합니다.

---

3. set bit 개수가 목표보다 많은 경우 (제거 작업)

while (setBitsCount > targetSetBitsCount) {
    if (isSet(result, currentBit)) {
        unsetBit(result, currentBit);
        setBitsCount--;
    }
    currentBit++;
}

• 목적:
  만약 num1에 있는 1비트의 개수가 target보다 많다면,
  결과에서 일부 1비트를 낮은 자리부터 제거하여 num1과의 값 차이를 작게 유지합니다.

• 동작:

  • 앞에서 추가 작업 후 currentBit는 이미 증가한 상태일 수 있으므로,
    그 이후의 비트부터 검사하게 됩니다.
  • 만약 result의 currentBit 자리가 1이면, 이를 0으로 변경합니다.
  • 제거할 때마다 setBitsCount를 1 감소시킵니다.
  • setBitsCount가 targetSetBitsCount와 같아질 때까지 이 과정을 반복합니다.

왜 낮은 자리부터?
낮은 자리(최하위 비트)는 수의 값에 미치는 영향이 작으므로,
비트를 추가하거나 제거할 때 num1과의 값 차이가 작아져 최종 XOR 값이 최소화됩니다.

---

4. 최종 결과 반환

return result;

• 조정된 result는 이제 num2와 동일한 개수의 set bit를 가지면서 num1과 최대한 유사한 값이 됩니다.
• 이 수를 반환함으로써, num1과 result의 XOR 값이 최소가 되는 결과를 얻을 수 있습니다.

---

5. 헬퍼 함수

코드의 마지막 부분에서는 세 개의 헬퍼 함수가 정의되어 있습니다:

• isSet(int x, int bit):
  주어진 정수 x의 bit번째 비트가 1인지 검사합니다.

  bool isSet(int x, int bit) { return x & (1 << bit); }

• setBit(int &x, int bit):
  정수 x의 bit번째 비트를 1로 설정합니다.

  void setBit(int &x, int bit) { x |= (1 << bit); }

• unsetBit(int &x, int bit):
  정수 x의 bit번째 비트를 0으로 만듭니다.

  void unsetBit(int &x, int bit) { x &= ~(1 << bit); }

이들 함수를 통해 비트 조작을 쉽게 수행할 수 있습니다.

---

결론

이 알고리즘은 num1의 비트를 조정하여

• num2의 set bit 개수와 맞추고,
• 가능한 한 num1과의 차이를 최소화(즉, 낮은 자리에서 수정)
  하는 방식으로 num1 XOR result의 값을 최소화합니다.

전체적으로,

1. num1의 현재 set bit 수와 num2의 set bit 수를 비교하여
2. 부족하면 낮은 자리부터 0인 비트를 1로 만들고,
3. 초과하면 낮은 자리부터 1인 비트를 0으로 바꾸어,
4. 목표 set bit 수에 맞추어 결과 값을 반환합니다.

Approach 2: Building the Answer

• 0ms, 8.05MB
• Complexity
  • Let $n$ be the maximum possible value of num1 or num2.
  • Time Complexity: $O(\log n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int result = 0;

        int targetSetBitsCount = __builtin_popcount(num2);
        int setBitsCount = 0;
        int currentBit = 31;  // Start from the most significant bit.

        // While x has fewer set bits than num2
        while (setBitsCount < targetSetBitsCount) {
            // If the current bit of num1 is set or we must set all remaining
            // bits in result
            if (isSet(num1, currentBit) ||
                (targetSetBitsCount - setBitsCount > currentBit)) {
                setBit(result, currentBit);
                setBitsCount++;
            }
            currentBit--;  // Move to the next bit.
        }

        return result;
    }

private:
    // Helper function to check if the given bit position in x is set (1).
    bool isSet(int x, int bit) { return x & (1 << bit); }

    // Helper function to set the given bit position in x to 1.
    void setBit(int &x, int bit) { x |= (1 << bit); }
};

GPT (o3-mini-high)

이 코드는 두 정수 num1과 num2가 주어졌을 때,
num2의 set bit 개수(1의 개수)와 동일한 set bit 개수를 가지면서,
num1와의 XOR 결과가 최소가 되는 정수 result를 만드는 문제를 해결합니다.

즉, 우리가 만들고자 하는 result는 아래 조건을 만족해야 합니다:

1. result의 1의 개수는 num2의 1의 개수와 같다.
2. result와 num1 사이의 비트 차이가 작아야 하므로, 가능한 한 num1의 비트와 일치하도록 result를 구성한다.

이 알고리즘은 비트 단위로 result를 구성하는데, 가장 중요한 아이디어는
“더 중요한(높은 자리) 비트부터 처리하면서,
num1에 이미 1이 설정된 자리라면 그대로 따라가고,
그렇지 않은 경우 남은 비트 자리가 부족하면 강제로 1을 설정하는”
방식으로 진행됩니다.

아래 단계별로 코드를 설명합니다.

---

1. 초기 설정

int result = 0;
int targetSetBitsCount = __builtin_popcount(num2);
int setBitsCount = 0;
int currentBit = 31;  // 가장 높은 비트(31번 비트)부터 시작.

• result: 최종 결과로 만들 정수. 초기값은 0이며,
  여기서 필요한 비트들을 하나씩 채워나갑니다.
• targetSetBitsCount:
  __builtin_popcount(num2)를 통해 num2의 set bit 개수를 구합니다.
• setBitsCount:
  현재까지 result에 설정된 1의 개수를 추적합니다.
• currentBit:
  비트 처리를 가장 높은 자리(31번 비트)부터 시작합니다.

---

2. 결과의 set bit 개수를 맞추기 위한 반복

while (setBitsCount < targetSetBitsCount) {
    // 현재 currentBit 위치에서:
    // 1) 만약 num1의 해당 비트가 1이면, result에도 1을 설정하여 num1과 일치시킵니다.
    // 2) 그렇지 않은 경우, 남은 비트 위치가 부족해 (남은 비트 위치 < 필요한 비트 수)
    //    반드시 이 자리부터 채워야 한다면 1을 설정합니다.
    if (isSet(num1, currentBit) ||
        (targetSetBitsCount - setBitsCount > currentBit)) {
        setBit(result, currentBit);
        setBitsCount++;
    }
    currentBit--;  // 다음 (조금 덜 중요한) 비트로 이동.
}

• 첫 번째 조건: isSet(num1, currentBit)
  → 만약 num1의 currentBit 위치가 이미 1이면,
  결과값도 그 자리를 1로 설정해서 num1과의 차이를 줄입니다.

• 두 번째 조건: (targetSetBitsCount - setBitsCount > currentBit)
  → 현재 남은 비트 위치(0부터 currentBit까지 총 currentBit+1개 중,
  코드에서는 currentBit와 비교하여 남은 공간이 부족한지 판단함)는
  앞으로 필요한 set bit을 모두 채울 수 없을 정도로 부족하다면,
  강제로 현재 자리부터 1로 채워 넣어야 함을 의미합니다.

  예를 들어, 만약 현재 currentBit == 3인데 아직 4개의 1을 채워야 한다면,
  0~3번 자리에는 총 4개의 비트가 있으므로, 현재 자리부터 반드시 1로 채워야 합니다.

• 반복문은 result에 targetSetBitsCount만큼의 1을 채울 때까지 진행됩니다.

---

3. 헬퍼 함수

두 헬퍼 함수는 비트 연산을 위한 간단한 도우미입니다.

• isSet(int x, int bit):
  주어진 정수 x의 bit번째 비트가 1인지 검사합니다.

  bool isSet(int x, int bit) { return x & (1 << bit); }

• setBit(int &x, int bit):
  정수 x의 bit번째 비트를 1로 설정합니다.

  void setBit(int &x, int bit) { x |= (1 << bit); }

---

4. 최종 결과 반환

return result;

반복문이 종료되면, result는 num2의 set bit 개수와 동일한 1의 개수를 가지면서
가능한 한 num1와 비슷하게 구성되었으므로,
num1 XOR result가 최소가 되는 수가 됩니다.

---

결론

• 목표: num2의 1의 개수를 그대로 반영하면서 num1과의 XOR 차이를 최소화하는 정수 result를 만든다.
• 방식:
  높은 자리부터 하나씩 채워나가는데,
  num1에 1이 있으면 그대로 result에도 1을,
  만약 그렇지 않더라도 앞으로 남은 자리가 부족하면 강제로 1을 설정합니다.
• 결과: 최종적으로 result는 targetSetBitsCount만큼 1을 가지며, num1과 최대한 일치하는 비트를 갖게 되어 XOR 값이 최소화됩니다.

이와 같이, 코드는 비트 단위로 결과를 구성하여 문제의 조건을 만족하는 최적의 수를 찾아냅니다.