BOJ 13505 두 수 XOR 풀이

문제 링크 

두 수의 XOR 연산이 가장 크기 위해선,

 

두 수를 각각 이진법으로 표현했을 때

 

같은 위치에 있는 숫자들은 한 쪽이 0이면 다른 쪽은 1, 한 쪽이 1이면 다른 쪽은 0이 되어야 한다.

 

예를 들어보자.

 

이진법으로 표현했을 때 101001 과 같은 숫자가 있고, 주어지는 숫자들은 모두 111111보다 작거나 같다는 보장이 있다면,

 

101001과 XOR 연산을 했을 때 가장 큰 숫자는 010110과 가장 차이가 적은 숫자가 된다.

 

이 가장 차이가 적은 숫자를 찾는 방법은 두 방법이 있다.

 

먼저, 첫 번째 방법을 알아보자. (wwiiiii님 풀이.)

 

숫자 k에 대해 k에 NOT 연산을 하여, k와 XOR을 했을 때, 최대값이 되는 숫자 k`을 구한다.

(int의 경우는 2진법 표현해서 첫번째 자리가 음, 양을 결정짓게되므로, NOT연산을 하고 1073741823 = 2^30-1 와 AND 연산을 하는 과정이 필요하다.)

 

그리고 k`과 가장 차이가 적은 값을 찾으면 되는데, 이건 벡터에 숫자들을 넣고 정렬한 뒤,

 

lower_bound 멤버 함수를 사용하면 쉽게 할 수 있다.

 

lower_bound의 결과로 나온 인덱스가 가리키고 있는 값은 k` 이상인 숫자 중에서 가장 차이가 적은 숫자이고,

lower_bound의 결과로 나온 인덱스의 바로 전 인덱스가 가리키고 있는 값은 k` 미만인 값들 중에서 가장 차이가 적은 숫자이다.

 

이 두 숫자에 대해서 XOR 연산을 하고, 최대값을 찾으면 된다.

 

이 방법의 시간복잡도는 숫자를 넣고, 정렬하는 과정만 생각하면 나머지는 부수적이므로 NlogN이다.

 

두 번째 방법으론 Trie를 활용하는 방법이 있다.

 

입력받는 각 숫자들을 Trie를 활용하여 이진법으로 바꿔서 저장한다.

 

그리고 각 숫자들에 대해서 큰 자릿수부터 반대 방향으로 내려갈 수 있으면 반대 방향으로(0이면 1로, 1이면 0으로), 아니면 그냥 원래 방향대로 가는 방식으로 XOR했을 때 가장 커지는 값을 찾을 수 있다.

 

이 방법의 시간복잡도는 입력받는 숫자들의 갯수 뿐만이 아니라, 숫자들의 크기에도 영향을 받는다.

 

Trie에 숫자들을 저장하고, 검색하는데 걸리는 시간을 생각해보면, '숫자들을 이진법으로 표현했을때의 길이'에 정비례하는 시간이 걸린다는 걸 알 수 있다.

 

따라서 이 방법의 시간복잡도는 NlogM (input의 범위가 0이상 M이하라고 할 때) 이 된다.

 

이 문제에선 숫자의 범위는 10^9이고, 숫자의 갯수는 10^5이므로, 첫 번째 방법이 더 좋은 방법이라 할 수 있겠다. 메모리가 덜 들기도 하고...

 

하지만 난 두번째 방법으로 풀어버렸다.

 

문제를 맞춘 경우에 wwiiiii님의 소스를 볼 수 있으니 참고하도록 하자.