13505 - 두 수 XOR (Trie)

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

13505번: 두 수 XOR

Trie를 계속해서 조져봅시다.

 

두 수 XOR, 이 문제는 Trie 문제인 것을 모르면, Trie까지 생각하기 힘든 문제입니다. 저는 심지어, Trie 문제인 것을 알고 봤는데도 어떻게 응용을 해야하는지 하루 내내 생각을 할 정도였어요 ㅠㅠ... 아직 한 참 모자랍니다.

 

어찌됐건, 이 문제에 어떻게 Trie를 끼얹을 수 있을까요?

결국 XOR이 최대한 크려면, 비교하려는 두 수의 같은 자릿값이 최대한 달라야 합니다. 그래야 2진수에 1이 많아지면서 숫자가 무럭무럭 자라니까요.

 

제가 헷갈린 부분은 뭐였나면, 결국 비교 당하는 수, 비교 하려는 수 이 두가지를 모두 알아가면서 비교해야하는 것입니다.

 

저는 비교 하려는 수를  Trie에 집어넣고, 비교 당하는 수를 배열에 저장해서 서로를 비교했죠.

 

비교전에, 비교하는 수, 비교하려는 수 모두 2진수로 변환을 해놓고 비교해야합니다, 또한, 비교하는 자릿수를 같게 만들기 위해서 저는 0을 앞에 채웠습니다.

 

예를 들어, 1과 8을 비교할 때, 0001, 1000을 비교했습니다. 1에 0을 앞에 다 채웠습니다.

 

비교를 할 땐 2가지의 고려 사항이 있습니다.

1. 비교 당하는 수가 0일 때, 비교 하는 수에 1이 존재하는가? => 서로 다르니, XOR의 결과로 1
2. 비교 당하는 수가 1일 때, 비교 하는 수에 0이 존재하는가? => 서로 다르니, XOR의 결과로 1
3. 위 2가지 경우가 아니면, 같은 수 밖에 없으니, XOR의 결과로 0

이후엔, 비교한 결과를 가지고 다시 10진수로 바꿔주면 됩니다. 여기까지는 여러분들 똑똑하니 이해하실거라고 믿습니다.

 

참고로 이 문제엔 endOfWord를 고려할 필요는 없습니다. 앞서 말했듯이 모든 숫자의 자릿수를 동일하게 만들었으니, 끝나는 지점은 다 동일하니까요.

 

제가 이 문제를 풀면서 가장 어려움을 가진 부분은 10진수를 2진수로 바꾸는 부분이었습니다.

 

처음에 바꿀 땐, 이렇게 하려 했습니다.

void deTotw(long long number, int n) {
	int idx = 0;
	while (number) {
		tmp[idx] = number % 2 + '0';
		number /= 2;
		idx++;
	}
	tmp[idx] = '\0';
	for (int i = 0; i < 8; i++) {
		if (i == 7) {
			word[n][i] = '\0';
		}
		else if (7 - i == idx) {
			--idx;
			word[n][i] = tmp[idx];
		}
		else word[n][i] = '0';
	}
}

word라는 배열에 집어넣는 방식인데, 정말 무식한 방법입니다. 만약 이렇게 하실 분이 계시다면 저는 말리고 싶습니다. 문제 풀기도 바쁜데, 잡아내야 하는 오류도 많을 뿐더러... 뭐랄까... 직관적이지 않다 해야하나? 문자형, 정수형을 바꿔가며 문제를 푸니까 버그도 많은 방법이었습니다.

디버깅을 잘 표현하는 짤

그러다, 검색하면서 발견한 방법인데, ㄹㅇ 이 방법이 진짜 꿀입니다.

long long power_2[31]

void initPower() {
	power_2[0] = 1;
	for (int i = 1; i < 31; i++) {
		power_2[i] = power_2[i - 1] * 2;
	}
}

void binaryToDecimal(long long input, int n) {
	for (int i = 30; i >= 0; --i) {
		if (input / power_2[i] == 1) {
			binary[n][30 - i] = 1;
			input -= power_2[i];
		}
		else binary[n][30 - i] = 0;
	}
}

power_2라는 배열엔 2의 배수들이 내림차순으로 들어가 있습니다. 그리고 저희가 변환을 원하는 숫자를 binaryToDecimal에 넣고 power_2에 있는 수를 나누어보면서 나누어지면 (몫이 1이면), 그 자릿 수에 1을 넣고, 아니면 0을 넣으면 됩니다.

 

[32, 16, 8, 4, 2, 1]이라는 power_2가 존재하고 30이라는 숫자를 이진수로 바꾼다면 [0, 1, 1, 1, 1, 0]이 되겠죠?

 

이부분만 잘 이해하고 넘어가신다면 충분히 푸실 수 있는 문제라고 생각합니다.

 

Trie를 동적으로 만들어가면서 풀어보았습니다.

#include <stdio.h>
#include <malloc.h>

typedef struct _trie {
	struct _trie* next[2];
} Trie;

Trie* root;

long long power_2[31], input, result = 0;
int binary[100000][31];
int N;

Trie* makeNode() {
	Trie* tmp= (Trie*)malloc(sizeof(Trie));
	tmp->next[0] = NULL;
	tmp->next[1] = NULL;
	return tmp;
}

void initPower() {
	power_2[0] = 1;
	for (int i = 1; i < 31; i++) {
		power_2[i] = power_2[i - 1] * 2;
	}
}

void binaryToDecimal(long long input, int n) {
	for (int i = 30; i >= 0; --i) {
		if (input / power_2[i] == 1) {
			binary[n][30 - i] = 1;
			input -= power_2[i];
		}
		else binary[n][30 - i] = 0;
	}
}

void insert(int n) {
	Trie* cur = root;
	for (int i = 0; i < 31; ++i) {
		if (!cur->next[binary[n][i]]) cur->next[binary[n][i]] = makeNode();
		cur = cur->next[binary[n][i]];
	}
}

long long find(int n) {
	Trie* cur = root;
	long long tmp = 0;
	for (int i = 0; i < 31; ++i) {
		if (binary[n][i] && cur->next[0]) {
			cur = cur->next[0];
			binary[n][i] = 1;
		}
		else if (!binary[n][i] && cur->next[1]) {
			cur = cur->next[1];
			binary[n][i] = 1;
		}
		else {
			cur = cur->next[binary[n][i]];
			binary[n][i] = 0;
		}
	}

	for (int i = 0; i < 31; i++) {
		if (binary[n][i]) tmp += binary[n][i] * power_2[30 - i];
	}

	return tmp;
}

int main(void) {
	root = makeNode();
	initPower();
	scanf("%d", &N);
	for (int n = 0; n < N; ++n) {
		scanf("%lld", &input);
		binaryToDecimal(input, n);
		insert(n);
	}
	for (int n = 0; n < N; ++n) {
		long long tmp = find(n);
		if (result < tmp) result = tmp;
	}
	printf("%lld", result);
}

 

아래 방법은 정적으로 푼 방법입니다.

#include <stdio.h>

int Trie[5000000][2], adr[1000000], binary[100000][31];
int N, ptr = 0;
long long power_2[31], input, result;

void initPower() {
	power_2[0] = 1;
	for (int i = 1; i < 31; ++i) {
		power_2[i] = power_2[i - 1] * 2;
	}
}

void decimalToBinary(long long input, int n) {
	for (int i = 0; i < 31; ++i) {
		if (input / power_2[30 - i]) {
			input -= power_2[30 - i];
			binary[n][i] = 1;
		}
		else binary[n][i] = 0;
	}
}

void insert(int n) {
	int cur = 0;
	for (int i = 0; i < 31; i++) {
		if (!Trie[cur][binary[n][i]]) Trie[cur][binary[n][i]] = ++ptr;
		cur = Trie[cur][binary[n][i]];
	}
}

long long find(int n) {
	int cur = 0;
	long long tmpNum = 0;
	for (int i = 0; i < 31; i++) {
		if (binary[n][i] && Trie[cur][0]) {
			cur = Trie[cur][0];
			binary[n][i] = 1;
		}
		else if (!binary[n][i] && Trie[cur][1]) {
			cur = Trie[cur][1];
			binary[n][i] = 1;
		}
		else {
			cur = Trie[cur][binary[n][i]];
			binary[n][i] = 0;
		}
		tmpNum += binary[n][i] * power_2[30 - i];
	}
	return tmpNum;
}

int main(void) {
	initPower();
	scanf("%d", &N);
	for (int n = 0; n < N; ++n) {
		scanf("%lld", &input);
		decimalToBinary(input, n);
		insert(n);
	}
	for (int n = 0; n < N; ++n) {
		long long tmpNum = find(n);
		if (result < tmpNum) result = tmpNum;
	}
	printf("%lld", result);
}

---

이상 13505 - 두 수 XOR (Trie)였습니다. ^_^