[BOJ] 백준 13505번 두 수 XOR (Java)

#13505 두 수 XOR

난이도 : 플레 3 

유형 : 자료구조/ 트라이

13505번: 두 수 XOR

▸ 문제

N개의 수가 주어졌을 때, XOR한 값이 가장 큰 두 수를 찾는 프로그램을 작성하시오.

즉, A1, A2, ..., AN 중에서 i ≠ j이면서 Ai XOR Aj 가 가장 큰 것을 찾아야 한다.

▸ 입력

첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 N개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다.

▸ 출력

첫째 줄에 XOR한 값이 가장 큰 두 수의 XOR한 결과를 출력한다.

 

문제 풀이  

사실상 트라이 유형 문제인지 모르고 풀었다면 과연 내가 트라이로 접근하는데 얼마나 걸렸을까 생각이 드는 문제이다. 브루트포스하게 값을 구한다면 연산 과정을 O(1)라고 가정해도 반복으로 돌리는 횟수만 N^2이므로 10만 x 10만으로 거의 100억번의 연산을 해야한다. 주어지는 수 N개를 줄일 수는 없으니 당연히 비교와 연산과정을 줄이는 방법을 생각해내야 하는데 그러면 트리 구조를 활용하는 방법을 생각해 볼 수 밖에 없다.

 

설계 및 구현

문제에서 주어지는 최댓값 1,000,000,000을 이진수로 바꾸면 111011100110101100101000000000(2)이다. 총 30자리 숫자이다. 그러면 트리는 0 또는 1 상태를 가지고 높이는 최대 30을 가지게 되므로 설계상 메모리는 크게 문제는 없을 것 같다. 

 

1,2,3,4,5를 트리에 이진수로 저장한다면 1, 01, 11, 100, 101의 데이터를 꼬리를 없애고 위에서부터 저장하고 싶지만 그러면 xor쿼리를 실행할 때 비교대상의 자릿수를 표현하기 애매해진다. 비교하는 데이터의 자릿수는 알 수 있지만 비교당하는 다른 N-1개의 데이터의 자릿수까지 계산하려면 여차저차 구한다해도 꽤나 복잡해질 것 같다. 그러므로 그냥 머리가 길어지더라도 모든 데이터를 30자리 이진수로 고정하고 순서대로 데이터를 넣어주도록 하자.

 

트리이 구조

트라이 구조는 childNode[0] 또는 childNode[1]을 가지는 방식으로 설계하였다. 만약 childNode가 없다면 해당 이진수는 없다고 보면 된다. 그리고 모두 30 높이로 고정하였기 때문에 terminal 여부도 필요없다.

static class TrieNode{
	TrieNode[] childNode = new TrieNode[2];
}

 

트라이 내부 함수

insert()메서드는 입력으로 주어진 num을 비트연산을 통해 (0또는 1) 자식노드를 생성해주면 된다.

public void insert(int num){
	TrieNode cur = this;
	for(int i=maxHeight; i>=0; i--) {
		int status = num & (1<<i);

		int nxt = status ==0? 0 : 1;
		if(cur.childNode[nxt] == null) {
			cur.childNode[nxt] = new TrieNode();
		}
		cur = cur.childNode[nxt];
	}
}

 

예시로 1, 2, 4, 8, 16, 32의 입력값을 트라이에 삽입하면 다음과 같이 저장된다.

 

트라이노드 데이터 저장 예시

1 >  0 000000000000000000000000000001
2 >   0000000000000000000000000000010
4 >   0000000000000000000000000000100
8 >   0000000000000000000000000001000
16 > 0000000000000000000000000010000
32 > 0000000000000000000000000100000

 

 

queryXOR()메서드는 입력으로 주어진 값을 넣어서 트라이에 저장된 모든 데이터와 xor연산을 하는 메서드이다. 이진수가 원래 순서에 맞게 차례대로 저장되어있기 때문에 그냥 순차적으로 xor연산을 해주면서 xor == 1인 값은 res에 저장하여 최종 출력해주면 된다.

public int queryXOR(int num) {
	TrieNode cur = this;
	int res =0;
	for(int i=maxHeight; i>=0; i--) {
		int status = num & (1<<i);

		int nxt = status ==0? 1 : 0; // xor이므로 반대로
		if(cur.childNode[nxt] == null) {
			nxt = nxt ==0 ? 1: 0; // 비교되는 값 없으므로 원상태로 복구
		}else {
			res += 1 <<i; 
		}
		cur = cur.childNode[nxt];
	}
	return res;
}

 

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int maxHeight = 30;
	static class TrieNode{
		TrieNode[] childNode = new TrieNode[2];
		
		public TrieNode(){
			/* no-op */
		}
		
		public void insert(int num){
			TrieNode cur = this;
			for(int i=maxHeight; i>=0; i--) {
				int status = num & (1<<i);
				int nxt = status ==0? 0 : 1;
				if(cur.childNode[nxt] == null) {
					cur.childNode[nxt] = new TrieNode();
				}
				cur = cur.childNode[nxt];
			}
		}
		
		public int queryXOR(int num) {
			TrieNode cur = this;
			int res =0;
			for(int i=maxHeight; i>=0; i--) {
				int status = num & (1<<i);
				int nxt = status ==0? 1 : 0; // xor이므로 반대로
				if(cur.childNode[nxt] == null) {
					nxt = nxt ==0 ? 1: 0; // 비교되는 값 없으므로 원상태로 복구
				}else {
					res += 1 <<i;
				}
				cur = cur.childNode[nxt];
			}
			return res;
		}
	}
    
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		TrieNode trie = new TrieNode();
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		List<Integer> inputData = new ArrayList<>();
		for(int i=0; i<n; i++) {
			int num = Integer.parseInt(st.nextToken());
			trie.insert(num);
			inputData.add(num);
		}
		
		int max= -1;
		for(int input : inputData) {
			int res = trie.queryXOR(input);
			max = Math.max(max, res);
		}
		
		System.out.println(max);
	}
	
}