문제 URL : https://www.acmicpc.net/problem/13505
13505번: 두 수 XOR
N개의 수가 주어졌을 때, XOR한 값이 가장 큰 두 수를 찾는 프로그램을 작성하시오. 즉, A1, A2, ..., AN 중에서 i ≠ j이면서 Ai XOR Aj 가 가장 큰 것을 찾아야 한다.
www.acmicpc.net
문제 접근법 :
단순무식하게 이중for문으로 xor을 진행한다면 시간초과가 발생합니다. n이 10만이라
그렇다면 다른방법으로 해야하는데 트라이 자료구조를 이용해야합니다.
솔직히 알고리즘 분류에서 트라이라는 내용 아니었으면 전혀 몰랐을겁니다. 그것을보고 힌트가되서 풀렸고
입력받은 수를 이진수로 표현합니다. 해당숫자가 5를 2진수로 101 이지만
실제로 c에선 int형일땐 0000~~0101 이라는 32bit로 표현하게됩니다. 그렇다고해서 trie의 깊이를 32까지는 할필요가없습니다. 문제 조건에서 입력값의 범위는 10억까지이고 2^30이 10억을 넘기니 깊이가 30이면 충분합니다.
그렇다면 xor한 값을 중에 어떻게 최대값을 찾냐면 trie에 모든입력값을 2진수화 한것을 집어넣은후
최상위 비트에서 최하위 비트로 내려오면서 해당 비트가 켜져있다면 꺼져있는 것을 찾으면되고
꺼져있다면 켜져있는방향으로 찾으면됩니다. 찾는다면 그값을 xor시켜주면 해당 비트가 켜지게 되어 최대값을
쉽게 찾을수 있습니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define M 30
vector<int> v;
int n;
struct trie {
trie* children[2];
trie() {
memset(children, 0, sizeof(children));
}
~trie() {
for (int i = 0; i < 2; i++)
if (children[i])delete children[i];
}
void insert(vector<int>& t, int height = 0) {
if (height >= M)return;
int next = t[height];
if (children[next] == NULL)
children[next] = new trie();
children[next]->insert(t, height + 1);
}
int find(vector<int>& t, int value,int height = 0) {
if (height >= M)return value;
int next = t[height];
//현재 해당비트가 켜져있거나 꺼져있다면 반대인것을 찾음
if (children[!next])
next = !next;
value ^= (next << (M - height - 1));//그것을 xor해준것이 최대값을 만듦
return children[next]->find(t, value, height + 1);
}
};
vector<int> tobinary(int value) {
vector<int> t(M);
for (int j = M - 1; j >= 0; j--) {
t[j] = value % 2;
value /= 2;
}
return t;
}
trie tr;
void input() {
cin >> n;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
v.push_back(num);
vector<int> t = tobinary(num);
tr.insert(t);
}
}
void solve() {
int res = 0;
for (int num : v) {
vector<int> t = tobinary(num);
res = max(res, tr.find(t,num));
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 8595 히든 넘버 (0) | 2021.08.22 |
|---|---|
| 백준 22351 수학은 체육과목 입니다3 (0) | 2021.08.22 |
| 백준 14906 스러피 (0) | 2021.08.19 |
| 백준 21610 마법사 상어와 비바라기 (0) | 2021.08.19 |
| 백준 13900 순서쌍의 곱의 합 (0) | 2021.08.16 |
