(13505) 두 수 XOR

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

단계별로 풀어보기

46단계(문자열 알고리즘 1) 6번째

 

 

 

두 수를 XOR한 결과값이 크려면 높은 자리에 있는 비트가 달라야 한다. 만약 가장 높은 자리 비트가 다른 쌍이 여럿이라면 그 다음 비트를 비교하고, 또 다른 쌍 중 다음 비트를 비교하고... 이런 식으로 탐색해야 한다.

따라서 트라이 자료 구조를 만든 뒤 높은 자리부터 역으로 집어넣는다. 수의 범위가 int 범위 이내이므로 적당히 31비트까지 넣어주면 된다.

트라이에 모든 수를 집어넣었다면 다시 모든 수를 하나씩 탐색하며 XOR한 결과의 최대값을 찾는다. 자신의 현재 자리 비트의 값과 다른 비트가 존재한다면 해당 자리에 XOR하여 1이 되는 수가 있다는 의미이므로 자리 비트에 해당하는 값을 더하고 반대 비트로 아래로 내려간다. 존재하지 않는다면 값 추가 없이 자신과 같은 비트로 아래로 내려간다.

 

 

 

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Trie {
  bool finish= false;
  Trie* next[2]= {nullptr, };
  ~Trie() { for(int i=0;i<2;i++)  if(next[i]!=nullptr)  delete next[i]; }
  
  void insert(const int n, int depth= 30){
    if(depth<0) { finish= true;  return; }
    
    int idx= (n&(1<<depth)) ? 1 : 0;
    if(next[idx]==nullptr)  next[idx]= new Trie();
    next[idx]->insert(n, depth-1);
  }
  
  int find(const int n, int depth= 30){
    if(depth<0)  return 0;
    
    int idx= (n&(1<<depth)) ? 1 : 0;
    if(next[!idx]==nullptr)  return next[idx]->find(n, depth-1);
    else  return (1<<depth)+next[!idx]->find(n, depth-1);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n);
  Trie* root= new Trie();
  int ans= 0;
  
  for(int i=0;i<n;i++){
    cin >> v[i];
    root->insert(v[i]);
  }
  
  for(int i=0;i<n;i++){
    ans= max(ans, root->find(v[i]));
  }
  
  cout << ans;
  
  return 0;
}

 

 

 

모든 수를 탐색하지 않고 한 번에 트라이를 탐색하는 방식도 있다. 두 개의 트라이를 최대한 다른 방향으로 내려가게 순회하며 최대값을 찾는 방식이다. 이때 두 트라이 각각 0과 1의 내려가는 노드가 모두 존재하는 경우, 0과 1로 내려가는 것과 1과 0으로 내려가는 것 중 뭐가 최대값이 될 지 모르기 때문에 두 경우 다 탐색해야 한다.

이전 코드보다 속도도 약간 빠르다.

#include <iostream>
#include <map>
using namespace std;

struct Trie {
  bool finish= false;
  Trie* next[2]= {nullptr, };
  ~Trie() { for(int i=0;i<2;i++)  if(next[i]!=nullptr)  delete next[i]; }
  
  void insert(const int n, int depth= 30){
    if(depth<0) { finish= true;  return; }
    
    int idx= (n&(1<<depth)) ? 1 : 0;
    if(next[idx]==nullptr)  next[idx]= new Trie();
    next[idx]->insert(n, depth-1);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  Trie* root= new Trie();
  
  for(int i=0;i<n;i++){
    int t;
    
    cin >> t;
    
    root->insert(t);
  }
  
  int res= 0, ans= 0;
  
  auto search= [&](auto self, Trie* A, Trie* B, int depth= 30) -> void {
    if(depth<0)  return;
    
    bool flag= true;
  
    if(A->next[0]!=nullptr && B->next[1]!=nullptr){
      flag= false;
      res|= (1<<depth);
      ans= max(ans, res);
      self(self, A->next[0], B->next[1], depth-1);
      res^= (1<<depth);
    }
    if(A->next[1]!=nullptr && B->next[0]!=nullptr){
      flag= false;
      res|= (1<<depth);
      ans= max(ans, res);
      self(self, A->next[1], B->next[0], depth-1);
      res^= (1<<depth);
    }
    if(flag && A->next[0]!=nullptr && B->next[0]!=nullptr){
      return self(self, A->next[0], B->next[0], depth-1);
    }
    if(flag && A->next[1]!=nullptr && B->next[1]!=nullptr){
      return self(self, A->next[1], B->next[1], depth-1);
    }
  };
  
  search(search, root, root);
  
  cout << ans;
  
  return 0;
}