[BOJ] 16903 수열과 쿼리 20

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

16903번: 수열과 쿼리 20

알고리즘: Trie

 

시간복잡도: $O(Mlog10^9)$

---

접근:

 

M이 20만으로 꽤 크다. 따라서 매 쿼리마다 빠른 시간 안에(log) 해결해야한다.

여기서 주요 연산이 XOR 라는 것에 주목했다.

 

어차피 문제가 되는건 3번 쿼리다. (1, 2번은 단순 추가/삭제니...)

A에 있는 모든 원소와 XOR 연산을 하고 최댓값을 구해야한다.

 

두가지 관찰만 하면 풀이에 쉽게 접근할 수 있다.

 

1. XOR 연산은 같은 비트는 0, 서로 다른 비트는 1로 만든다. (0^0 = 1^1 = 0, 0^1 = 1^0 = 1)

2. 최댓값은 이진수로 표현했을 때, 제일 왼쪽에 1이 있는 수다.

 

-> A^x 의 값이 최대가 되는 A는 x와 비교했을 때 제일 왼편에 있는 비트가 다른 수다.

-> x의 비트를 반대로 뒤집으면, 왼쪽 비트부터 A와 비교했을 때 가장 유사도가 높아야한다.

 

Trie를 만들고 x의 비트를 반대로 뒤집어 순회하는 방식으로 최댓값을 찾아냈다.

 

---

 

 

	// 16903: 수열과 쿼리 20
	// fail1: pop에서 cnt 감소를 리프노드에서만 실행함(for문 밖에 써버림)
	#include<iostream>
	using namespace std;
	struct node
	{
	node *l, *r; // left: 0, right: 1
	int cnt;
	node()
	{
	l = r = NULL;
	cnt = 0;
	}
	};
	struct XOR_tree
	{
	node *root;
	XOR_tree()
	{
	root = new node();
	node *x = root;
	for (int i = 30; i >= 0; --i) // 0 하나 추가
	{
	if (!(x->l)) x->l = new node();
	x = x->l;
	x->cnt = x->cnt + 1;
	}
	}
	void push(int val)
	{
	node *x = root;
	for (int i = 30; i >= 0; --i)
	{
	if (val & (1<<i))
	{
	if (!(x->r)) x->r = new node();
	x = x->r;
	}
	else
	{
	if (!(x->l)) x->l = new node();
	x = x->l;
	}
	x->cnt = x->cnt + 1;
	}
	}
	void pop(int val)
	{
	node *x = root;
	for (int i = 30; i >= 0; --i)
	{
	if (val & (1<<i)) x = x->r;
	else x = x->l;
	x->cnt = x->cnt - 1;
	}
	}
	int query(int val)
	{
	node *x = root;
	int ans = 0;
	for (int i = 30; i >= 0; --i)
	{
	if (val & (1<<i))
	{
	if (x->l && x->l->cnt)
	{
	x = x->l;
	ans |= 1<<i;
	}
	else x = x->r;
	}
	else
	{
	if (x->r && x->r->cnt)
	{
	x = x->r;
	ans |= 1<<i;
	}
	else x = x->l;
	}
	}
	return ans;
	}
	}tree;
	int M, q, x;
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
	cin >> q >> x;
	if (q == 1) tree.push(x);
	else if (q == 2) tree.pop(x);
	else cout << tree.query(x) << "\n";
	}
	return 0;
	}

view raw BOJ_16903.cpp hosted with ❤ by GitHub

 

---

Trie는 나중에 공부해야지 하고 미뤘었는데 문제에서 요구하는걸 그대로 구현하다보니,

자연스럽게 익히게 되었다 개꿀~