[BaekJoon] 13505번 - 두 수 XOR [Java][C++]

문제 링크

---

1. 문제 풀이

$N$ 개의 수에 대해 XOR 연산의 결과가 가장 큰 두 수를 찾는 문제로 트라이 자료구조를 활용하면 해결할 수 있다. XOR 연산은 두 수의 각 비트가 다를수록 값이 커지기 때문에 트라이에 각 수를 2진수 문자열로 저장하고 탐색은 각 자릿수에 대해 다른 비트를 우선으로 탐색하면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int MX = 1 + 100000 * 32;
    static final int ROOT = 0;
    static int unused = ROOT + 1;
    static int[][] nxt = new int[MX][2];

    static void insert(int x) {
        int cur = ROOT;
        for (int i = 31; i >= 0; i--) {
            int b = (x >> i) & 1;
            if (nxt[cur][b] == 0) nxt[cur][b] = unused++;
            cur = nxt[cur][b];
        }
    }

    static int find(int x) {
        int cur = ROOT;
        int res = 0;

        for (int i = 31; i >= 0; i--) {
            int b = (x >> i) & 1;
            if (nxt[cur][1 - b] != 0) {
                res |= (1 << i);
                cur = nxt[cur][1 - b];
            } else {
                cur = nxt[cur][b];
            }
        }

        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int max = 0;

        st = new StringTokenizer(br.readLine());
        while (n-- > 0) {
            int x = Integer.parseInt(st.nextToken());
            max = Math.max(max, find(x));
            insert(x);
        }

        System.out.println(max);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 100000 * 32;
const int ROOT = 0;
int unused = ROOT + 1;
int nxt[MX][2];

void insert(int x) {
    int cur = ROOT;
    for (int i = 31; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (nxt[cur][b] == 0) nxt[cur][b] = unused++;
        cur = nxt[cur][b];
    }
}

int find(int x) {
    int cur = ROOT;
    int res = 0;

    for (int i = 31; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (nxt[cur][1 - b]) {
            res |= (1 << i);
            cur = nxt[cur][1 - b];
        } else {
            cur = nxt[cur][b];
        }
    }

    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int mx = 0;
    while (n--) {
        int x;
        cin >> x;

        mx = max(mx, find(x));
        insert(x);
    }

    cout << mx;
}

---