BOJ 11338 - XOR Sum 링크
(2023.04.18 기준 G4)

문제

Q개의 쿼리가 주어진다. 쿼리에 알맞게 처리하기.
1. insert N : 숫자 목록에 N 추가
2. print : 숫자 목록 중 K개(K개가 아니라면 전부)의 수의 XOR 합을 출력

알고리즘

주어지는 수 중 K개까지의 큰 수를 저장해야 하므로 우선순위 큐
그리고 K가 최대 100,000이라 print 쿼리가 나올 때마다 일일이 XOR 합을 구하면 TLE다.
그러므로 XOR의 성질을 잘 이용하자.

풀이

K개까지의 큰 수를 저장하는 것은 어렵지 않다.
숫자 목록을 우선순위 큐로 다루자.
숫자 목록이 K개 미만일 경우엔 N을 그냥 push, 아니면 N이 숫자 목록의 제일 작은 수보다 크다면? 제일 작은 그 수를 pop하고 N을 push하면 된다.

문제는 XOR 합.
XOR 연산은 비트의 반전이다. 같은 비트를 두 번 반전시키면? 똑같다. 즉, A = A ^ B ^ B 이다.
그러므로 insert 쿼리가 들어오고 숫자 목록에 변동이 있을 때마다 나가는 수와 들어오는 수를 합에 XOR 연산해주면 된다. 그러면 그 합은 결국 K개까지의 숫자 목록의 XOR 합이 된다.

코드

• C++

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

void solve(){
    int Q, K;
    cin >> Q >> K;

    priority_queue<int, vector<int>, greater<int>> queue; // K개까지의 큰 수들
    string q; int N, XOR = 0; // XOR sum
    while (Q--){
        cin >> q;
        if (q[0] == 'p') cout << XOR << '\n'; // query print
        else{ // query insert N
            cin >> N;
            if (queue.size() < K) // 수가 K개를 넘지 않았다면 N을 그대로 넣어준다.
                XOR ^= N, queue.push(N);
            else if (queue.top() < N){ // N이 K개의 큰 수 중에서 제일 작은 수보다 크다면
                XOR ^= queue.top(), queue.pop(); //  K개의 큰 수 중에서 제일 작은 수를 빼주고
                XOR ^= N, queue.push(N); // N을 넣어준다.
            }
        }
    }
}

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

    int T;
    cin >> T;
    while (T--) solve();
}

• Python

import sys; input = sys.stdin.readline
from heapq import heappop, heappush

for _ in range(int(input())):
    Q, K = map(int, input().split())

    queue = [] # K개까지의 큰 수들
    xor = 0 # XOR sum
    for _ in range(Q):
        query = input().split()
        if len(query) == 1: # query print
            print(xor)
        else: # query insert N
            N = int(query[1])
            if len(queue) < K: # 수가 K개를 넘지 않았다면 N을 그대로 넣어준다.
                xor ^= N
                heappush(queue, N)
            elif queue[0] < N: # N이 K개의 큰 수 중에서 제일 작은 수보다 크다면
                xor ^= heappop(queue) # K개의 큰 수 중에서 제일 작은 수를 빼주고
                xor ^= N # N을 넣어준다.
                heappush(queue, N)