(추가예정) [Baekjoon/Python3/C++] 13505번 두 수 XOR

[Baekjoon/Python3] 13505번 두 수 XOR

 

www.acmicpc.net/problem/13505

13505번: 두 수 XOR

 

[Python3]

-

 

[C++]

#include <cstdio>
#include <algorithm>

int integerarr[100001];
char bit[33];

//trei의 한 노드를 나타내는 객체
typedef struct TrieNode {
	TrieNode* node[2];
	//종료 노드인가?
	bool finish;

	TrieNode() : finish(false) {
		node[0] = node[1] = NULL;
	}

	~TrieNode() {
		if (node[0]) delete node[0];
		if (node[1]) delete node[1];
	}

	//이 노드를 루트로 하는 trei에 문자열 key를 추가한다.
	void insert(const char* key) {
		//문자열이 끝나면 finish를 참으로 바꾸고 종료
		if (*key == 0)
			finish = true;
		else {
			int next = *key - '0';
			//해당 자식 노드가 없다면 생성한다.
			if (node[next] == NULL)
				node[next] = new TrieNode();
			//해당 자식 노드로 재귀호출
			node[next]->insert(key + 1);
		}
	}

	void query(char* key) {
		if (finish) return;
		int next = *key - '0';
		next ^= 1;
		if (node[next]) {
			*key = '1';
			node[next]->query(key + 1);
		}
		else {
			*key = '0';
			node[next ^ 1]->query(key + 1);
		}
	}
};

//pow function
int pow(int value1, int value2)
{
	int a = 1;
	while (value2)
	{
		if (value2 & 1)
			a *= value1;
		value2 >>= 1;
		value1 *= value1;
	}
	return a;
}


//max function
int max(int value1, int value2)
{
	int a;
	if (value1 >= value2)
		a = value1;
	else
		a = value2;
	return a;
}

int main() {
	int n, ans = 0;
	TrieNode *root = new TrieNode();
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", integerarr + i);
	for (int i = 0; i < n; i++) {
		int x = integerarr[i];
		for (int j = 31; j >= 0; j--) {
			bit[j] = '0' + (x & 1);
			x /= 2;
		}
		bit[32] = 0;
		root->insert(bit);
	}

	for (int i = 0; i < n; i++) {
		int x = integerarr[i];
		for (int j = 31; j >= 0; j--) {
			bit[j] = '0' + (x & 1);
			x /= 2;
		}
		bit[32] = 0;
		root->query(bit);
		int ans2 = 0;
		for (int j = 31; j >= 0; j--)
			ans2 += (bit[j] - '0') * pow(2, 31 - j);	//<algorithm>
		ans = max(ans, ans2);
	}
	printf("%d", ans);
}