구간에서 만들 수 있는 최대 XOR 값

자바스크립트 코딩테스트 문제로 linear-basis 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard linear-basis 함수명: rangeMaxSubsetXorQueries 제한 시간: 600ms

정수 배열 nums와 구간 질의 queries가 주어집니다.

문제 설명

각 질의 [left, right]마다 nums[left]부터 nums[right]까지의 숫자 중 일부를 골라 XOR 했을 때 만들 수 있는 가장 큰 값을 구하는 rangeMaxSubsetXorQueries 함수를 작성하세요.

부분집합은 비어 있어도 됩니다. 비어 있는 부분집합의 XOR 값은 0입니다.

예를 들어 nums = [3, 10, 5]인 구간에서는 10 ^ 5 = 15를 만들 수 있으므로 최대 XOR 값은 15입니다.

제한사항

1 <= nums.length <= 50000
0 <= nums[i] < 2^30
1 <= queries.length <= 50000
각 질의는 [left, right] 형태입니다.
0 <= left <= right < nums.length
반환값은 각 질의의 답을 입력 순서대로 담은 배열입니다.
브라우저 실행 환경을 고려해 질의마다 구간을 전부 다시 훑는 풀이는 시간 제한을 통과하기 어렵습니다.

예시

입력: nums = [3, 10, 5, 25, 2], queries = [[0, 4], [0, 2], [3, 3], [1, 4]] -> 출력: [31, 15, 25, 30]
입력: nums = [7, 7, 7], queries = [[0, 2], [1, 1]] -> 출력: [7, 7]
입력: nums = [0, 1, 2, 4, 8], queries = [[0, 0], [1, 4], [2, 3]] -> 출력: [0, 15, 6]

힌트

XOR에서 어떤 수가 이미 다른 수들의 XOR 조합으로 만들어진다면, 최대값을 만드는 데 반드시 따로 보관할 필요는 없습니다.
각 비트의 최고 자리부터 보며 선형 독립인 수만 남기는 XOR 선형 기저를 생각해 보세요.
세그먼트 트리의 각 노드에 해당 구간의 선형 기저를 저장하면, 질의 구간을 덮는 노드들의 기저만 병합해 답을 만들 수 있습니다.

해설

핵심은 한 구간 안에서 만들 수 있는 모든 XOR 값을 직접 나열하지 않는 것입니다.

XOR 선형 기저는 숫자들을 비트 벡터처럼 보고, 서로 XOR 조합으로 만들 수 없는 대표 숫자만 남긴 구조입니다. 새 숫자 x를 넣을 때는 가장 높은 비트부터 확인합니다. 해당 비트를 가진 기저가 이미 있으면 x를 그 기저와 XOR 해서 최고 비트를 낮춥니다. 끝까지 줄였는데 x가 0이 아니라면, 그 숫자는 기존 기저로 만들 수 없는 새 조합이므로 그 최고 비트 위치의 기저로 저장합니다.

한 번 기저를 만들면 최대 XOR 값은 높은 비트부터 greedy하게 계산할 수 있습니다. 현재 답 best에 어떤 기저 값을 XOR 했을 때 값이 더 커진다면 그 기저를 사용합니다. 높은 비트를 먼저 키우는 선택이 항상 더 큰 정수를 만들기 때문입니다.

여러 구간 질의를 빠르게 처리하려면 세그먼트 트리를 사용합니다.

리프 노드에는 원소 하나로 만든 선형 기저를 저장합니다.
내부 노드는 왼쪽 자식의 기저에 오른쪽 자식의 기저 원소들을 차례로 삽입해 만듭니다.
질의 [left, right]가 들어오면 해당 범위를 덮는 노드들의 기저를 하나의 임시 기저로 병합합니다.
임시 기저에서 만들 수 있는 최대 XOR 값을 계산해 답 배열에 넣습니다.

기저의 크기는 숫자의 비트 수만큼, 여기서는 최대 30개입니다. 따라서 기저 병합 비용은 상수에 가까운 O(30^2)이고, 각 질의는 세그먼트 트리의 O(log n)개 노드만 확인합니다.

전체 시간 복잡도는 대략 O((n + q) log n * 30^2)이며, nums.length와 queries.length가 큰 경우에도 모든 구간을 매번 직접 순회하는 방식보다 훨씬 안정적입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과