문제 설명
숫자 리스트 nums와 쿼리 리스트가 주어지며, 각 쿼리는 [x, limit] 형태입니다. 각 쿼리에 대해 다음 작업을 수행해야 합니다.
- nums에서 e ≤ limit 조건을 만족하는 요소 e를 찾습니다.
- 그중 e XOR x 값이 가장 커지는 요소를 선택합니다.
- 조건을 만족하는 요소가 하나도 없으면 -1을 반환합니다.
예를 들어 nums = [3, 5, 9], queries = [[4, 6], [2, 0]]이라면 결과는 [3, -1]입니다. 첫 번째 쿼리(x=4, limit=6)에서는 6 이하인 3과 5가 후보입니다. 3 XOR 4 = 7이고 5 XOR 4 = 1이므로, 더 큰 XOR 값을 만드는 3을 선택합니다. 두 번째 쿼리(x=2, limit=0)에서는 0 이하인 숫자가 없으므로 -1을 반환합니다.
풀이 접근 방법
이 문제는 비트 트라이(Trie)와 오프라인 쿼리 처리 기법을 함께 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 숫자를 32비트 이진수로 변환해 트라이에 삽입하고, 말단 노드에 해당 숫자 자체를 저장합니다.
- XOR 값을 최대화하려면 각 비트 단계에서 현재 비트와 반대되는 값(0이면 1, 1이면 0)을 가진 자식 노드가 있는지 우선 확인합니다.
- limit 조건 때문에 모든 숫자를 미리 넣을 수 없으므로, 숫자 배열과 쿼리를 limit 기준으로 정렬한 뒤 필요한 숫자만 순서대로 트라이에 추가하면서 쿼리를 처리합니다.
알고리즘 단계
- bits(i): 정수 i를 32자리 이진 표현으로 변환해 반환합니다.
- insert(i): 트라이 루트에서 시작해 bits(i)의 각 비트를 따라 내려가며 노드를 생성하고, 마지막 노드에 key 2로 실제 값 i를 저장합니다.
- query(i): 루트에서 시작해 각 비트마다 반대 비트(rc = c XOR 1)를 가진 자식이 있으면 그쪽으로, 없으면 같은 비트 자식으로 이동합니다. 도착한 노드에 저장된 값이 XOR 최댓값을 만드는 숫자입니다.
- 메인 흐름: 배열 A를 오름차순 정렬하고, 쿼리를 (인덱스, x, limit) 형태로 만들어 limit 기준으로 정렬합니다. 포인터 j를 두고 A[j] ≤ limit인 동안 계속 insert한 뒤, 트라이가 비어 있지 않으면 query(x)로 답을 채웁니다.
Python 구현 예제
다음 코드를 통해 동작 방식을 더 명확히 이해할 수 있습니다.
class Solution:
def solve(self, A, queries):
trie = {}
def bits(i):
return map(int, bin(i)[2:].zfill(32))
def insert(i):
node = trie
for c in bits(i):
node = node.setdefault(c, {})
node[2] = i
def query(i):
node = trie
for c in bits(i):
rc = c ^ 1
node = node.get(rc, node.get(c))
return node[2]
A.sort()
B = sorted([(i, x, limit) for i, (x, limit) in enumerate(queries)], key=lambda x: x[2])
j, n, ans = 0, len(A), [-1] * len(queries)
for i, x, limit in B:
while j < n and A[j] <= limit:
insert(A[j])
j += 1
if j:
ans[i] = query(x)
return ans
ob = Solution()
nums = [3, 5, 9]
queries = [
[4, 6],
[2, 0]
]
print(ob.solve(nums, queries))
실행 결과
입력:
[3, 5, 9], [[4, 6], [2, 0]]
출력:
[3, -1]
복잡도 분석
- 정렬 비용: O(N log N + Q log Q)
- 삽입·질의 비용: 숫자당 32비트 순회 → O((N + Q) × 32)
- 전체 시간 복잡도: 약 O(N log N + Q log Q + 32(N + Q)) / 공간 복잡도: O(32N)