[BOJ/Platinum 3] 백준 13505 두 수 XOR(C++)

문제 링크

https://www.acmicpc.net/problem/13505

13505번: 두 수 XOR

 

문제

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

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

입력

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

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

출력

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

예제 입력 1

5
1 2 3 4 5

예제 출력 1

7

예제 입력 2

5
0 1 0 1 0

예제 출력 2

1

예제 입력 3

6
1 2 4 8 16 32

예제 출력 3

48

알고리즘 분류

• 트라이

풀이

정수들을 이진수로 변환하고 트라이에 insert한다.

그리고 각 이진수를 통해 트라이를 탐색하면서 최댓값을 구한다.

최댓값을 구하기 위해서는 높은 자리수부터 순차적으로 비트를 비교해서 최대한 1을 많이 갖도록 해야 한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 100001
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct TRIE {
    bool isEnd;
    LL finish_Number;
    TRIE* Child[2];

    TRIE() {
        isEnd = false;
        for (int i = 0; i < 2; i++) {
            Child[i] = nullptr;
        }
    }

    void insert_Pattern(string Pattern, LL Number) {
        TRIE* NowTrie = this;

        for (int i = 0; i < Pattern.size(); i++) {
            int Now = Pattern[i] - '0';

            if (NowTrie->Child[Now] == nullptr) {
                NowTrie->Child[Now] = new TRIE;
            }

            NowTrie = NowTrie->Child[Now];
        }

        NowTrie->isEnd = true;
        NowTrie->finish_Number = Number;
    }

    LL query(string NowS, LL NowN) {
        LL Result = NowN;
        TRIE* NowTrie = this;

        for (int i = 0; i < NowS.size(); i++) {
            int Now = NowS[i] - '0';
            if (NowTrie->Child[Now ^ 1] != nullptr) {
                NowTrie = NowTrie->Child[Now ^ 1];
            }
            else {
                NowTrie = NowTrie->Child[Now];
            }
        }

        Result ^= NowTrie->finish_Number;
        return Result;
    }
};

int N;
LL A, Max_Length;
vector<LL> Numbers;
vector<string> Strings;
LL Answer;

string make_String(int Number) {
    string Result = "";
    while (1) {
        if (Number == 0) {
            break;
        }

        Result = to_string(Number % 2) + Result;
        Number /= 2;
    };

    return Result;
}

void settings(TRIE* Root) {
    for (int i = 0; i < N; i++) {
        string Now = Strings[i];
        int NowL = (int)Now.length();
        int Sub = Max_Length - NowL;
        string tmp = "";
        while (Sub--) {
            tmp += '0';
        };
        Strings[i] = tmp + Now;
        Root->insert_Pattern(Strings[i], Numbers[i]);
    }
    for (int i = 0; i < N; i++) {
        TRIE* NowTrie = Root;
        string NowS = Strings[i];
        int NowN = Numbers[i];
        Answer = max(Answer, NowTrie->query(NowS, NowN));
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

void input() {
    TRIE* Root = new TRIE();
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A;
        Numbers.push_back(A);
        string NewA = make_String(A);
        Strings.push_back(NewA);
        Max_Length = max(Max_Length, (LL)NewA.length());
    }
    settings(Root);
    find_Answer();
    delete Root;
}

int main() {
    FASTIO
    input();

    return 0;
}