[백준/BOJ] 백준 13505번 : 두 수 XOR

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

13505번: 두 수 XOR

입력받은 수들을 이진수의 문자열로 만들고, 가장 긴 문자열을 기준으로 같은 길이의 문자열로 만들어서 트라이에 넣은 뒤 트라이를 통해 문제를 해결했는데, 어떤 숫자와 XOR연산으로 가장 큰 수를 만들 수 조합의 숫자는 앞쪽의 비트가 먼저 반전이 되는 경우일수록 큰 수를 만들 수 있다는 것을 이용하여 문제를 해결했다.

 

코드

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

struct node {
	bool finish;
	int finish_number;
	node* children[2];
};

node* MakeNode() {
	node* ret = new node();

	ret->finish = false;
	for (int i = 0; i < 2; i++)
		ret->children[i] = NULL;

	return ret;
}

int n;
node* root;
vector<int> input1s;
vector<string> input2s;
long long max_len = 0;

//이진수 문자열로 반환
string MakeInput2(int input1) {

	string ret = "";

	while (1)
	{
		if (input1 == 0)
			break;

		ret = to_string((input1 % 2)) + ret;
		input1 = input1 / 2;
	}

	return ret;
}

void Insert(node*& here, int input1, string& input2, int index)
{
	if (index == input2.size())
	{
		here->finish = true;
		here->finish_number = input1; //해당 지점에서 끝나는 수를 저장
		return;
	}

	if (here->children[input2[index] - '0'] == NULL)
		here->children[input2[index] - '0'] = MakeNode();

	Insert(here->children[input2[index] - '0'], input1, input2, index + 1);
}

long long Query(node*& here, int input1, string& input2, int index)
{
	//input1과 XOR해서 가장 큰 값을 만들 수 있는 수의 위치로 왔을때 (트라이의 끝 위치)
	if (index == input2.size())
	{
		//현재 비교하는 수와 해당 위치의 수를 XOR연산
		return (((long long)here->finish_number) ^ ((long long)input1));
	}

	//해당 비트가 반전되는 경우가 있을때
	//그쪽으로 움직인다 (이진수의 앞부터 확인하므로 가장 먼저 반전되는 경우를 찾아가는게 좋다)
	if (here->children[(input2[index] - '0') ^ 1] != NULL)
	{
		return Query(here->children[(input2[index] - '0') ^ 1], input1, input2, index + 1);
	}

	//해당 비트가 반전되는 경우가 없을때
	//일단 있는 숫자 쪽으로 움직인다
	else
	{
		return Query(here->children[(input2[index] - '0')], input1, input2, index + 1);
	}

}

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

	//트라이 루트를 만든다
	root = MakeNode();

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input1;
		cin >> input1;

		string input2 = MakeInput2(input1); //입력받은 수를 이진수로 변환한 문자열

		input1s.push_back(input1);
		input2s.push_back(input2);

		max_len = max(max_len, (long long)input2.size()); //가장 긴 문자열의 길이를 저장
	}

	for (int i = 0; i < n; i++)
	{
		string input2 = input2s[i];
		int input1 = input1s[i];

		//가장 긴 문자열이 아닐때
		if (input2.size() < max_len)
		{
			//앞에 추가로 0을 붙인다 (모든 이진수를 같은 길이로 만든다)
			string add = "";
			for (int i = 0; i < max_len - input2.size(); i++)
			{
				add += '0';
			}
			input2 = add + input2;
		}

		Insert(root, input1, input2, 0);
	}

	long long result = 0;
	for (int i = 0; i < n; i++)
	{
		string input2 = input2s[i];
		int input1 = input1s[i];

		if (input2.size() < max_len)
		{
			string add = "";
			for (int i = 0; i < max_len - input2.size(); i++)
			{
				add += '0';
			}

			input2 = add + input2;
		}

		result = max(result, Query(root, input1, input2, 0));
	}

	cout << result;

	return 0;
}