파이썬(Python)으로 각 쿼리별 최대 XOR 값 구하는 프로그램

크기가 n인 배열 nums와 하나의 값 m이 주어져 있다고 가정해 보겠습니다. 우리는 다음과 같은 작업을 n번 반복해서 수행해야 합니다.

• nums의 모든 원소와 k를 XOR 연산했을 때 결과가 최대가 되는 음이 아닌 정수 k(단, k < 2^m)를 찾습니다. 이때 찾은 k가 i번째 쿼리의 답이 됩니다.

• 현재 배열 nums에서 마지막 원소를 제거합니다.

• answer[i]가 i번째 쿼리의 답이 되도록 배열 answer를 완성합니다.

예를 들어 입력이 nums = [0,1,1,3], m = 2라면 출력은 [0,3,2,3]이 됩니다. 그 과정을 살펴보면 다음과 같습니다.

• nums = [0,1,1,3]일 때, 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3이므로 k = 0입니다.

• nums = [0,1,1]일 때, 0 XOR 1 XOR 1 XOR 3 = 3이므로 k = 3입니다.

• nums = [0,1]일 때, 0 XOR 1 XOR 2 = 3이므로 k = 2입니다.

• nums = [0]일 때, 0 XOR 3 = 3이므로 k = 3입니다.

문제 해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• x := 2^m − 1로 초기화합니다.

• i를 0부터 nums의 길이 − 1까지 반복하면서 다음을 수행합니다.

  • nums[i] := nums[i] XOR x

  • x := nums[i]

• 배열을 뒤집은 결과를 반환합니다.

이 알고리즘이 동작하는 핵심 원리는 다음과 같습니다. 모든 원소가 2^m보다 작으므로 XOR 연산으로 만들 수 있는 최댓값은 2^m − 1입니다. 따라서 각 시점에 남아 있는 원소들의 전체 XOR 값을 P라고 할 때, P XOR k = 2^m − 1이 되도록 하는 k, 즉 k = P XOR (2^m − 1)이 곧 답이 됩니다. 위 알고리즘은 누적 XOR(prefix XOR)을 활용해 이 값을 효율적으로 계산하고, 마지막에 배열을 뒤집어 쿼리 순서에 맞는 결과를 만들어냅니다.

예시 코드

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

def solve(nums, m):
   x=2**m-1
   for i in range(len(nums)):
      nums[i]^= x
      x = nums[i]
   return(nums[::-1])

nums = [0,1,1,3]
m = 2
print(solve(nums, m))

입력

[0,1,1,3], 2

출력

[0, 3, 2, 3]