[Leetcode 1829번 문제] 1829. Maximum XOR for Each Query

문제 상황

You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:

1. Find a non-negative integer k < 2maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the ith query.
2. Remove the last element from the current array nums.

Return an array answer, where answer[i] is the answer to the ith query.

배열이 존재하고 특정한 정수 maximumBit이 있다. 이하의 작업을 n번 반복한다

1. 처음부터 끝까지의 요소를 XOR한 수와 2 ^ maximumBit 보다 작은 수를 XOR해 나올 수 있는 최대의 수를 answer에 추가한다.
2. 마지막 요소를 pop한다

이럴때 나올 수 있는 배열을 리턴하라

입력

• nums.length == n
• 1 <= n <= 105
• 1 <= maximumBit <= 20
• 0 <= nums[i] < 2maximumBit
• nums is sorted in ascending order.

출력

각각의 query의 결과를 담은 배열

과정

각각의 쿼리를 잘 생각해보자 우선 직렬화가 가능하다, nums 처음부터 끝까지를 xor해놓고 쿼리하나를 할때마다 그 수를 back의 수와 xor하면 된다. 그럼 그 각각의 xor수와 xor하였을 때 가장 큰 수가 나올 수 있게 하는 수는 뭘까?

특정 수를 이진수화 하게되면 각 자리수가 1또는 0인 수가 될 것이다

ex ) 1011010101

여기서 예시 수보다 작은수를 한정할때 최고 높은 수를 만들어낼 수 있는 방법은 예제수가 1인비트의 자리는 0이고 0인자리는 1인 수다.

ex)0100101010

이런 결과가 나오는건 XOR이 (나만 가지고있는 수)만을 남기기 때문이다. 즉 자리수가 얼마나 되든 서로의 자리수의 1이 겹치지 않게 조절만 해주면 가장 큰 수를 결과물로 만들 수 있다. 그러면 서로의 자리수가 겹치지 않게하는 수는 어떻게 구할 수 있을까?

가능한만큼 가장 큰 자리의 수중 모든 자리가 1인 수(1111, 111)를 원래의 수와 XOR연산을 하면된다.

이 수를 주어진 수와 XOR할경우 주어진수의 1의 자리수는 다 0으로 바뀌고 0인부분만 1로 생길 것이기 때문이다.

설령 k가 주어진 수보다 크더라도 마찬가지이다

다행히 주어진 수 k의 최대값은 2 ^ n의 형태로 주어진다. 이점을 이용해서, 2 ^ n - 1과 주어진 XOR수를 XOR하면 원하는 수를 구할 수 있다

알고리즘

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int xorS = 0;
        for (int num : nums)
        {
            xorS ^= num;
        }
        vector<int> answer;
        int maxNum = pow(2, maximumBit) - 1;
        while (!nums.empty())
        {
            int ans = 0;
            int idx = 0;
            int idxBit = 1;
            answer.push_back(xorS ^ maxNum);
            xorS ^= nums.back();
            nums.pop_back();
        }
        return answer;
    }
};