LeetCode 1707. Maximum XOR With an Element From Array

문제

leetcode.com/problems/maximum-xor-with-an-element-from-array/

Maximum XOR With an Element From Array - LeetCode

풀이과정

주어진 숫자의 개수가 10^5 이고, 쿼리의 개수도 10^5 이므로, 각 쿼리에 대해서 주어진 수를 일일이 검사하여 최적의 해를 구하는 방법은 O(|N||Q|) = 10^10 으로 TLE를 피할 가능성이 없다.

각 쿼리에서 제시한 수 x 대해서 bitwise XOR이 최대가 되는 수는 x의 각 bit에 대해 반대 bit를 취한 값이다. 예를 들어 x가 10100110이라면, x와 bitwise XOR 연산 결과가 최대가 되는 수는 01011001이다. 문제는 조건없이 연산결과가 최대가 되는 수를 찾는 것이 아니라, 주어진 수 중에서 찾아야 한다는 것이다.

주어진 수를 most significant bit 부터 least significant bit 순으로 각 비트를 선택할 수 있도록 trie를 구성하고(Trie라는 자료구조명을 잊고 있었다가, 문제를 풀고 난 후 discussion을 살펴 보면서 자료구조 이름을 기억해냈다. 솔루션에서 Trie를 만드는 함수명이 buildTrie() 가 아니라 buildTree() 인 이유도 코드 작성 당시에는 자료구조명을 기억하고 있지 않았기 때문이다.), 쿼리에서 제시한 수 x의 각 비트마다 반대 비트를 취할 수 있으면 반대 비트를 취하고, 그렇지 않은 경우 어쩔 수 없이 같은 비트를 선택하는 방법으로 trie leaf노드까지 내려가면 주어진 수 중 x 와 bitwise XOR 연산값이 최대가 되는 수를 구할 수 있다.

문제에 각 쿼리마다 bitwise XOR 연산을 할 대상 숫자가 넘지말아야할 상한이 주어진다. Trie를 만들때, 각 노드에 그 노드를 root로 하는 sub tree가 표현할 수 있는 모든 숫자중 가장 작은 값을 기억하게 한다. 검색 도중 sub tree의 최소값이 상한보다 큰 경우 해당 sub tree를 선택하지 않는 방법으로 조건을 만족할 수 있다.

솔루션

#include <vector>
#include <cstdio>
using namespace std;

struct V {
    V(): min(0), b0(NULL), b1(NULL) {}

    int min;
    V* b0;
    V* b1;
};

void buildTree(int x, V* root) {
    V* v = root;
    for (int i = 0; i <= 30; ++i) {
        int b = !!(x & (1 << (30-i)));
        v->min = min(v->min, x);
        if (b == 0) {
            if (v->b0 == NULL) {
                v->b0 = new V();
                v->b0->min = x;
            }
            v = v->b0;
        } else {
            if (v->b1 == NULL) {
                v->b1 = new V();
                v->b1->min = x;
            }
            v = v->b1;
        }
    }
}

int solve(int x, int m, V* root) {
    V* v = root;
    int i = 0;
    int ans = 0;
    for (int i = 0; i <= 30; ++i) {
        int b = !!(x & (1 << (30-i)));
        if (b == 0) {
            if (v->b1 != NULL && v->b1->min <= m) {
                ans |= (1 ^ b) << (30 - i);
                v = v->b1;
            } else if (v->b0 != NULL && v->b0->min <= m) {
                ans |= (0 ^ b) << (30 - i);
                v = v->b0;
            } else {
                return -1;
            }
        } else {
            if (v->b0 != NULL && v->b0->min <= m) {
                ans |= (0 ^ b) << (30 - i);
                v = v->b0;
            } else if (v->b1 != NULL && v->b1->min <= m) {
                ans |= (1 ^ b) << (30 - i);
                v = v->b1;
            } else {
                return -1;
            }
        }
    }
    return ans;
}

class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> res;
        V* root = new V();
        root->min=1000000000;
        for (int num : nums) {
            buildTree(num, root);
        }
        for (auto& query : queries) {
            res.push_back(solve(query[0], query[1], root));
        }
        return res;
    }
};

회고

회고 1

Trie라는 자료구조를 잊고 있었다가 discussion을 보면서 자료구조 이름을 기억해 냈다. 문제 풀이 도중 trie를 사용하지 못했던 것은 아니지만, 자료구조를 기억하고 있었더라면 좀 더 빨리 솔루션을 생각해 낼 수 있었을 것이다. 복습의 중요성을 깨닫는다.

en.wikipedia.org/wiki/Trie

Trie - Wikipedia

회고 2

Discussion을 보면, query가 offline이라는 특성을 활용한 최적화가 눈에 띈다.

query를 상한을 기준으로 정렬을 하고 해당 상한을 넘지않는 숫자만으로 trie를 덧붙여 나가면 trie에서 서브트리의 최소값을 저장하는 구현 없이 깔끔하게 구현이 가능해 진다.

query는 오름차순으로 처리하고  마지막에 원래의 순서로 재정렬하여 리턴하면 된다.