[P3] 백준 13505번 두 수 XOR C++ 트라이, 트리

리뷰

 

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

최대 10만로 주어지는 N개의 수 중 두개의 수를 XOR연산 했을때 가장 큰 값을 찾는 문제

알고리즘 분류에 트라이라고 명시되어있지 않았다면 절대 트라이로 접근 못했을 것 같다.

 

전역 변수

• LOG : 입력으로 주어지는 수 최대 10억을 비트로 자릿수를 계산하기 위한 정수형 상수 변수
• n : 입력으로 주어지는 숫자의 개수를 저장할 변수
• ans : 두 수의 XOR한 결과 중 가장 큰 값을 저장할 변수
• Trie : 트라이를 통해 비트로 구성된 트리를 관리하기 위한 구조체

 

함수

1. Insert

void Insert(Trie* node, const string& str)

 

1, 0으로 이루어진 문자를 트리에 삽입하는 함수

1. 매개변수로 root의 노드 node와 비트 형식의 문자열 str을 받는다.
2. Trie* 변수 cur에 node값을 할당하고 문자열의 고정 개수인 LOG의 수만큼 반복문을 개행한다.
3. idx를 문자열의 각 문자에서 '0'을 뺀 값으로 초기화 해준다.
4. 만약 현재 노드의 자식 중 idx가 없다면 새롭게 할당해 준다.
5. idx에 해당하는 child로 cur을 이동시켜 준다.

 

2. Query

void Query(Trie* node, const string& str, int temp)

 

현재 구성된 트리 내에서 XOR한 최대 값을 찾는 함수

1. 매개변수는 Insert함수와 동일하며 기본값 0을 temp로 받아준다. 함수 내부에서 변수로 정의해도 무방하다.
2. for문 개행과 idx를 정의하는 것 까지는 Insert 함수와 동일하다.
3. 만약 자식 노드에서 현재 문자와 반전된 값이 존재한다면
4. temp에 2^LOG-i-1 값을 더해준다, 이후 다음 노드는 반전된 노드로 이동시킨 뒤 continue처리해 준다.
5. 만약 자식 노드에 현재 idx값이 존재하지 않는다면 새로 경로를 추가하고 temp를 위와 같이 증가시킨다.
6. cur을 자식노드의 idx로 이어서 탐색을 진행해 준다.
7. 모든 탐색을 마친 후 ans와 temp를 비교하여 더 큰 값을 ans에 저장해 준다.

 

3. getBit

string getBit(int n)

 

정수를 입력하고 비트 형식의 문자열로 파싱 후 리턴하는 함수

1. 매개변수로 정수 n을 입력 받는다, 빈 문자열 s를 초기화 하고 LOG-1 ~ 0까지의 for문을 개행한다.
2. 만약 n의 i번째 비트가 1이라면 s에 1을 더해준다, 0이라면 0을 더해준다.
3. 완성된 문자열을 리턴해 준다.

 

문제풀이

1. Tire타입의 root변수에 Trie를 동적할당 해준다.
2. 정수형 변수 first를 초기화 해주고 n과 first에 값을 받아준다, first는 첫번째 노드를 의미한다.
3. getBit함수를 통해 first에 저장된 정수형 변수를 비트 형식의 문자열 f로 변환해준다.
4. root에서부터 f문자열을 Insert해준다, 이때 ans는 굉장히 큰 값이 할당될 것이다.
5. 첫번째 숫자는 비교할 대상이 없기 때문에 현재 ans는 무의미 하므로 0으로 다시 초기화 해준다.
6. n - 1번의 반복문을 실행하며 num을 받아준다, 해당 정수를 동일하게 getBit으로 문자열 s로 치환해 준다.
7. Insert함수를 통해 root로부터 문자열 s를 트라이 트리에 추가해 준다.
8. Query함수를 통해 root로부터 문자열 s를 탐색하며 다른 노드와 비교로 생성된 XOR의 최대값을 탐색해 준다.
9. 모든 탐색을 마친 후 ans변수에 저장된 값을 출력해 준다.

 

참고 사항

입력으로 주어지는 수는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다.

분류가 트라이 이므로 해당 값을 비트형식으로 파싱하면 되겠다 라는 생각을 떠올리면 접근하기 쉽다.

 

 

정답 코드

#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;

const int LOG = 31;
int n, ans;

struct Trie {
    Trie* child[2] = { 0, };
};

void Insert(Trie* node, const string& str) {
    Trie* cur = node;
    for (int i = 0; i < LOG; i++) {
        int idx = str[i] - '0';
        if (!cur->child[idx]) cur->child[idx] = new Trie();
        cur = cur->child[idx];
    }
}

void Query(Trie* node, const string& str, int temp) {
    Trie* cur = node;
    for (int i = 0; i < LOG; i++) {
        int idx = str[i] - '0';

        if (cur->child[idx ^ 1]) {
            temp += pow(2, LOG - i - 1);
            cur = cur->child[idx ^ 1];
            continue;
        }

        if (!cur->child[idx]) {
            cur->child[idx] = new Trie();
            temp += pow(2, LOG - i - 1);
        }

        cur = cur->child[idx];
    }
    ans = max(ans, temp);
}

string getBit(int n) {
    string s = "";
    for (int i = LOG - 1; i >= 0; i--) {
        if ((n >> i) & 1) s += '1';
        else s += '0';
    }
    return s;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Trie* root = new Trie();
    int first;
    cin >> n >> first;

    string f = getBit(first);
    Insert(root, f);

    ans = 0;
    while (--n) {
        int num; cin >> num;
        string s = getBit(num);
        Insert(root, s);
        Query(root, s, 0);
    }

    cout << ans;
}