[백준] 13505 두 수 XOR

문제

N개의 수가 주어졌을 때, XOR한 값이 가장 큰 두 수를 찾는 프로그램을 작성하시오.

즉, A1, A2, ..., AN 중에서 i ≠ j이면서 Ai XOR Aj 가 가장 큰 것을 찾아야 한다.

입력

첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 N개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 XOR한 값이 가장 큰 두 수의 XOR한 결과를 출력한다.

 

주어지는 숫자들을 2진수로 바꾸고, 그 숫자들을 이용해 트라이를 구성합니다.

이때 그 숫자들의 길이를 맞춰주어야 합니다. 예를들어,,, 32 =10000 와 1=1이 있을때 트라이에

10000와 00001을 넣어야 합니다.

이런식으로 구성한 트라이에

각 숫자의 보수(complement)를 하나씩 넣어봅니다. 만약 00001=>11110을 넣을때 트라이에 순서대로 그 숫자가 존재하면 

string 에 1을 더하고 없으면 0을 더합니다.

그런식으로 만들어진 string이 XOR의 이진수입니다. 그 이진수의 최댓값을 출력하면 답입니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
char rev(char c) {
    if (c == '0')return '1';
    return '0';
}
struct Trie {
    bool output;
    Trie* go[2];
    Trie() {
        fill(go, go + 2, nullptr);
        output = false;
    }
    ~Trie() {
        rep(i, 2)
            if(go[i])
                delete go[i];
    }
    void insert(string str) {
        if (!str.length()) {
            output = 1;
            return;
        }
        int next = str[0] - '0';
        if (!go[next]) {
            Trie* newTrie = new  Trie;
            go[next] = newTrie;
        }
        go[next]->insert(str.substr(1));
    }
    string query(string str) {
        if (!str.length())return "";
        string ret;
        int cur = rev(str[0])-'0';
        if (go[cur]) {
            ret.push_back('1');
            ret.append(go[cur]->query(str.substr(1)));
        }
        else {
            ret.push_back('0');
            if (cur == 0) {
                ret.append(go[1]->query(str.substr(1)));
            }
            else {
                ret.append(go[0]->query(str.substr(1)));
            }
        }
        return ret;
    }
};
int N, maxlen = 1;
vector<string>strings;
int main() {
    FAST;
    cin >> N;
    rep(i, N) {
        int x;
        cin >> x;
        string str;
        int len = 1;
        while (x > 1) {
            str.push_back('0'+x % 2);
            x /= 2;
            len++;
        }
        maxlen = max(maxlen, len);
        if(x!=0)
            str.push_back('1');
        strings.push_back(str);
    }
    Trie* root = new Trie;
    for (string &str : strings) {
        int len = str.length();
        for (int i = 0; i < maxlen - len; i++) {
            str.push_back('0');
        }
        reverse(str.begin(), str.end());
        root->insert(str);
    }
    int ans = 0;
    for (string str: strings) {
        string temp = root->query(str);

        int val = 0;
        for (int i = 0; i < maxlen; i++) {
            if (temp[i] == '1') {
                val += pow(2, maxlen - 1 - i);
            }
        }
        ans = max(ans, val);
    }
    cout << ans;
}