1829. Maximum XOR for Each Query

Problem : https://leetcode.com/problems/maximum-xor-for-each-query

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:04:49

 

---

 

문제 설명

 

n개의 음이 아닌 정수로 구성된 정렬된 배열 nums와 정수 maximumBit를 입력으로 받는다. n개의 쿼리를 수행한다.

* 음이 아닌 정수 k를 찾는다. 이 때 k는 nums[0] ~ nums[nums.leingth-1]의 XOR값을 최대화시키는 값이다. k는 i번째 쿼리의 정답이다.

* nums의 가장 마지막 원소를 제거한다.

 

answer 배열을 반환하라. 이 때 answer의 i번째 원소는 i번째 쿼리의 정답이다.

---

 

풀이

 

XOR의 성질을 이용해서 풀이해보자.

 

• XOR의 연산은 두 수의 모든 비트가 서로 다를 때 최대가 된다.
  •  두 수의 모든 비트가 서로 다를 때는 빠르게 구할 수 있다. 2^n - (현재 xor 결과) - 1 꼴이기만 하면 된다.
    
• 즉 k를 상수 시간복잡도로 바로 구할 수 있다.
• 쿼리를 1번째부터 끝까지 순서대로 구할 필요는 없다. nums를 순서대로 순회하며, xor값을 누적하여 재사용하면 빠르게 결과를 구할 수 있다. 이 경우 결과를 저장하면 끝번째부터 1번째로 순서가 반대가 된다. 이 점을 유념하면 된다.

 

풀이 코드

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        xor = 0
        result = []
        for n in nums :
            xor = xor ^ n
            result.append(2 ** maximumBit - xor - 1)
            
        return list(reversed(result))