[LeetCode] 1829. Maximum XOR for Each Query

https://leetcode.com/problems/maximum-xor-for-each-query/description/?envType=daily-question&envId=2024-11-08

leetcode - Maximum XOR for Each Query

문제 유형: 비트마스킹, 비트 조작, 부분합

문제 난이도: Medium

 

문제

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.

 

정렬된 정수 배열 nums가 주어집니다. n개의 요소를 갖습니다. 정수 maximumBit도 받습니다.

당신은 쿼리를 n번 수행합니다:

1. 음이아닌 정수k (k < 2 ^ maximumBit, k = nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k를 최대로 하는값)를 쿼리의 응답으로 한다.
2. 배열에서 마지막 요소를 제거한다.

answer[i]가 i번째쿼리의 응답인 배열 answer를 반환하시오.

 

풀이

[0]부터 [남은배열길이-1]까지의 XOR값을 A라고 해보자.

A XOR k의 최대값은, k의 조건에 의해서 (1 << maximumBit) -1이 최대이다. 이를 target이라 하자.

즉, A와 target의 XOR값이 쿼리의 답이 된다.(XOR의 성질에 의해, A와 k는 1의보수 관계여야 XOR시 target이 된다.)

 

처음에 모든 수들의 xor을 구해놓고, 쿼리 응답을 구해서 응답 배열에 저장한 뒤, 맨 뒤 요소들부터 다시 xor 플립을 해주면서 제외하는 연산을 취하면 된다. 이를 n번 반복한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int x = 0, target = (1 << maximumBit) - 1;
        for (int num : nums) x ^= num; 

        vector<int> ans(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            ans[nums.size() - 1 - i] = x ^ target;
            x ^= nums[i];
        }

        return ans;
    }
};