[BaekJoon] 16903번 - 수열과 쿼리 20 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 배열에 대해 추가, 삭제, XOR 최댓값을 구해야 하는 문제로 트라이 자료구조를 활용해서 해결할 수 있다. 각 수를 2진수 문자열로 다루어 삽입, 삭제를 구현하고 XOR의 경우 서로 다른 비트일수록 값이 커지기에 이에 맞게 탐색을 해주면 된다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

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

    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];
            cnt[cur]++;
        }
    }

    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 && cnt[nxt[cur][1 - b]] > 0) {
                res |= (1 << i);
                cur = nxt[cur][1 - b];
            } else {
                cur = nxt[cur][b];
            }
        }

        return res;
    }

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

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

        int m = Integer.parseInt(br.readLine());
        insert(0);

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int q = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            if (q == 1) {
                insert(x);
            } else if (q == 2) {
                erase(x);
            } else {
                sb.append(find(x)).append("\n");
            }
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

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

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

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];
        cnt[cur]++;
    }
}

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] && cnt[nxt[cur][1 - b]] > 0) {
            res |= (1 << i);
            cur = nxt[cur][1 - b];
        } else {
            cur = nxt[cur][b];
        }
    }

    return res;
}

void erase(int x) {
    int cur = ROOT;
    for (int i = 31; i >= 0; i--) {
        int b = (x >> i) & 1;
        cur = nxt[cur][b];
        cnt[cur]--;
    }
}

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

    int m;
    cin >> m;

    insert(0);
    while (m--) {
        int q, x;
        cin >> q >> x;

        if (q == 1) {
            insert(x);
        } else if (q == 2) {
            erase(x);
        } else {
            cout << find(x) << '\n';
        }
    }
}

---