[P3] 백준 수열과 쿼리 20 C++ 트라이

리뷰

 

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

트라이를 활용한 XOR문제

 

 

전역 변수

• MB : 비트의 상한값을 저장할 상수 변수
• Trie : 트라이 관련 구조체, 두 비트를 나타낼 child배열과 현재 노드의 개수 cnt를 정의한다. Trie의 생성자는 child와 cnt배열을 0으로 초기화 해준다. 소멸자는 자식 노드 포인터를 모두 delete해준다.

 

함수

1. insert

void insert(Trie* root, const string& str)

 

트라이에 비트 값을 추가할 함수

매개 변수로 트라이의 루트 노드와 32개 비트 정보를 문자열로 입력 받는다.

root부터 타고 내려가면서 bit정보를 저장해주고, 각 참조한 노드마다 cnt를 증가시켜 준다.

만약 타고 내려가던 중 child가 nullptr일 경우 트라이를 동적으로 할당하고 주소값을 저장해 준다.

 

2. remove

void remove(Trie* root, const string& str)

 

트라이에서 비트 값을 삭제할 함수

1. 매개 변수로 트라이의 루트 노드와 32개 비트 정보를 문자열로 입력 받는다.
2. root부터 타고 내려가면서 bit정보에 해당하는 노드의 주소를 par배열에 입력 해준다, 또한 비트 정보는 bits배열에 저장해 주고, 매 노드마다 cnt를 1만큼 감소시켜 준다.
3. 이제 다시 리프노드로 부터 위로 올라가며 cnt가 0인 노드들에 대한 삭제 및 부모 노드의 참조 주소를 nullptr로 변경한다.

3. XOR

int XOR(Trie* root, const string& str)

 

배열 내 모든 요소와 XOR한 값 중 가장 큰 값을 구하는 함수

1. 매개 변수로 트라이의 루트 노드와 32개 비트 정보를 문자열로 입력 받는다.
2. root부터 타고 내려가면서 현재 bit와 반대되는 bit가 있다면 해당 노드로 진행하고 result에 비트만큼 쉬프트 연산한 값을 더해준다.
3. 현재 bit와 반대되는 bit가 없다면 현재 bit와 동일한 노드로 진행한다.
4. 존재하지 않을 경우 break를 걸어 두었는데 문제에선 그런 경우는 없다고 나타나 있다.
5. 탐색을 마친 후 result에 저장된 값을 리턴해 준다.

4. trans

string trans(int n)

 

정수를 비트 정보 문자열로 변환하는 함수

1. 매개 변수로 변환하기 위한 정수 n을 전달 받는다.
2. 쉬프트 연산을 통해 32개 비트 정보를 문자열로 변환하고 해당 문자열을 반환한다.

 

문제풀이

1. 트라이의 루트 노드를 동적 할당하여 초기화 후 초깃값 0을 trans로 바꾸어 insert처리해 준다.
2. m값을 입력 받고, m번의 while 루프를 돌려 매 루프마다 op와 n에 값을 입력 받아준다.
3. trans 함수에 n을 전달하여 반환 받은 비트 문자열을 변수 s에 저장해 준다.
4. op가 1이라면 insert 함수에 root, s를 전달해 트라이에 삽입해 준다.
5. op가 2이라면 insert 함수에 root, s를 전달해 트라이에서 제거해 준다.
6. op가 3이라면 XOR 함수에 root, s를 전달해 XOR의 최대값을 뽑아 출력해 준다.

 

트러블 슈팅

1. 처음엔 예제값이 잘 나오지 않았는데 remove시 cnt가 0일 경우 delete만 했던 것이 원인이었다.
2. delete와 동시에 부모 노드의 child의 bit값을 참조해 nullptr로 변경해 주어야 했다.

 

참고 사항

• 입력으로 주어지는 x의 범위는 109보다 작거나 같은 자연수이다.
• 삭제 쿼리는 항상 A에 x가 있는 쿼리만 주어진다.

 

정답 코드

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int MB = 32;
struct Trie {
	Trie* child[2];
	int cnt;
	Trie() {
		memset(child, 0, sizeof(child));
		cnt = 0;
	}
	~Trie() {
		if (child[0]) delete child[0];
		if (child[1]) delete child[1];
	}
};

void insert(Trie* root, const string& str) {
	Trie* cur = root;
	for (int i = 0; i < MB; ++i) {
		int bit = str[i] - '0';
		if (!cur->child[bit]) cur->child[bit] = new Trie();
		cur = cur->child[bit];
		cur->cnt++;
	}
}

void remove(Trie* root, const string& str) {
	Trie* cur = root;
	Trie* par[MB + 1];
	int bits[MB];
	par[0] = root;
	for (int i = 0; i < MB; ++i) {
		int bit = str[i] - '0';
		bits[i] = bit;
		cur = cur->child[bit];
		par[i + 1] = cur;
		cur->cnt--;
	}
	for (int i = MB; i > 0; --i) {
		if (!par[i]->cnt) {
			delete par[i];
			par[i - 1]->child[bits[i - 1]] = nullptr;
		}
	}
}

int XOR(Trie* root, const string& str) {
	Trie* cur = root;
	int result = 0;
	for (int i = 0; i < MB; ++i) {
		int bit = str[i] - '0';
		if (cur->child[bit ^ 1]) {
			result += 1 << 31 - i;
			cur = cur->child[bit ^ 1];
		}
		else if (cur->child[bit]) cur = cur->child[bit];
		else break;
	}
	return result;
}

string trans(int n) {
	string s = "";
	for (int i = 31; i >= 0; --i) {
		if (n & (1 << i)) s += '1';
		else s += '0';
	}
	return s;
}

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

	Trie* root = new Trie();
	insert(root, trans(0));
	int m; cin >> m;
	while (m--) {
		int op, n; cin >> op >> n;
		string s = trans(n);
		if (op == 1) insert(root, s);
		else if (op == 2) remove(root, s);
		else cout << XOR(root, s) << "\n";
	}
}