취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24397번 문제인 말해 xor NO!이다.

문제는 아래 링크를 확인하자.

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

xor 연산은 이진수의 각 자리 적용되는 연산이므로 주어지는 수들을 31자리의 이진수의 형태로 생각해보자.

말해 카드에 적힌 N개의 숫자를 31자리 이진수들로 나타내고, 어떤 숫자 x가 주어졌을 때 이 x와의 xor값이 K 미만인 숫말해 카드의 숫자의 개수를 빠르게 구할 수 있다면 이 문제는 간단히 해결할 수 있다.

만약 x와 N개의 숫자들을 각각 xor하여 K와 직접 비교한다면 O(N)의 시간이 걸릴 것이다. 이는 문제를 해결하는 데에 충분하지 않다.

그 대신, N개의 숫자들을 0과 1로 이루어진 31자리 문자열을 관리하는 trie와 같은 형태로 저장하고, 가장 큰 자릿수서부터 이진수로 나타난 K의 각 자리와 비교해나가며 개수를 센다면 이 trie의 깊이에 비례하는 시간이 걸릴 것이다. 이는 문제해결에 충분한 시간이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;

struct node {
	int cnt = 0;
	node* l = nullptr, *r = nullptr;
};

node* root;

void nodeinsert() {
	stack<int> stkN;
	int x; cin >> x;
	for (int i = 0; i < 31; i++) {
		stkN.push(x & 1);
		x >>= 1;
	}

	node* nodept = root;
	while (!stkN.empty()) {
		int current = stkN.top(); stkN.pop();
		if (current) {
			if (nodept->r == nullptr) nodept->r = new node;
			nodept = nodept->r;
		}
		else {
			if (nodept->l == nullptr) nodept->l = new node;
			nodept = nodept->l;
		}
		nodept->cnt++;
	}
}

int N, Q, K;
ll ans = 0;

void query() {
	stack<int> stkN, stkK;
	int x, k = K; cin >> x;
	for (int i = 0; i < 31; i++) {
		stkN.push(x & 1), stkK.push(k & 1);
		x >>= 1, k >>= 1;
	}

	node* nodept = root;
	while (!stkN.empty() && nodept!=nullptr) {
		x = stkN.top(); stkN.pop();
		k = stkK.top(); stkK.pop();
		if (k == 1) {
			if (x == 0) {
				if (nodept->l != nullptr) ans += nodept->l->cnt;
				nodept = nodept->r;
			}
			else {
				if (nodept->r != nullptr) ans += nodept->r->cnt;
				nodept = nodept->l;
			}
		}
		else {
			if (x == 0) nodept = nodept->l;
			else nodept = nodept->r;
		}
	}
}

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

	root = new node;

	cin >> N >> Q >> K;
	while (N--) nodeinsert();
	while (Q--) query();

	cout << ans;
}