[BaekJoon] 13504번 - XOR 합 [Java][C++]

문제 링크

---

1. 문제 풀이

부분 수열의 XOR 값의 최대를 찾는 문제로 트라이 자료구조를 활용하면 해결할 수 있다.

부분 수열의 경우 연속한 구간을 말하는데 누적 합에서 구간의 합을 누적 합의 차로 계산하듯이 누적 XOR도 구간의 XOR 값을 누적 XOR의 XOR 연산으로 구할 수 있다. 이를 위해 수열의 XOR 값을 누적시키며 트라이에서 가장 XOR 값이 큰 누적 XOR을 찾아 출력하고 새로운 누적값을 트라이에 삽입하는 과정을 반복하면 해결할 수 있다.

---

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;
    static int[][] nxt;

    static void init() {
        unused = ROOT + 1;
        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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            init();

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

            int max = 0;
            int pxor = 0;
            insert(pxor);

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

                max = Math.max(max, find(pxor));
                insert(pxor);
            }

            sb.append(max).append("\n");
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

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

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

void init() {
    unused = ROOT + 1;
    memset(nxt, 0, sizeof(nxt));
}

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 t;
    cin >> t;

    while (t--) {
        init();

        int n;
        cin >> n;

        int mx = 0;
        int pxor = 0;
        insert(pxor);

        while (n--) {
            int x;
            cin >> x;
            pxor ^= x;

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

        cout << mx << '\n';
    }
}

---