배열 A가 주어졌다고 가정해 봅시다. A의 모든 요소는 m번씩 반복되지만, 단 하나의 요소만 딱 한 번 나타납니다. 우리의 목표는 바로 이 고유한 요소를 찾아내는 것입니다.
예를 들어 입력이 A = [6, 2, 7, 2, 2, 6, 6]이고 m = 3이라면, 6과 2는 각각 3번씩 나타나므로 출력 결과는 7이 됩니다.
문제 해결 접근 방법
이 문제는 비트 연산을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 고유하지 않은 요소들은 모두 m번씩 등장하기 때문에, 특정 비트 위치에서 1이 설정된 횟수를 전체 배열에 대해 세면 그 값은 m의 배수이거나 m의 배수 + 1이 됩니다. 여기서 '+1'은 고유한 요소가 해당 비트를 가지고 있는 경우에 발생합니다. 따라서 각 비트별 개수를 m으로 나눈 나머지를 모으면 고유한 요소를 복원할 수 있습니다.
구체적인 단계는 다음과 같습니다.
- INT_SIZE := 정수형 변수의 크기 × 8 (즉, 정수의 비트 수)
- INT_SIZE 크기의 count 배열을 정의하고 0으로 초기화합니다.
- i := 0부터 i < INT_SIZE까지 반복하면서:
- j := 0부터 j < size까지 반복하면서:
- (arr[j] AND 2^i)의 결과가 0이 아니라면 count[i]를 1 증가시킵니다.
- j := 0부터 j < size까지 반복하면서:
- res := 0으로 초기화합니다.
- i := 0부터 i < INT_SIZE까지 반복하면서 res := res + ((count[i] mod m) × 2^i)를 누적합니다.
- res를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n × 비트 수), 즉 일반적인 32비트 정수 기준으로 O(32n)이며, 추가 메모리는 비트 개수에 비례하는 상수 공간만 필요합니다.
더 나은 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.
예제 (C++)
#include <bits/stdc++.h>
using namespace std;
int selectUnique(unsigned int arr[], int size, int m){
int INT_SIZE = 8 * sizeof(unsigned int);
int count[INT_SIZE];
memset(count, 0, sizeof(count));
for(int i = 0; i < INT_SIZE; i++)
for(int j = 0; j < size; j++)
if((arr[j] & (1 << i)) != 0)
count[i] += 1;
unsigned res = 0;
for(int i = 0; i < INT_SIZE; i++)
res += (count[i] % m) * (1 << i);
return res;
}
main(){
unsigned int arr[] = { 6, 2, 5, 2, 2, 6, 6 };
int size = sizeof(arr) / sizeof(arr[0]);
int m = 3;
cout << selectUnique(arr, size, m);
}입력
{ 6, 2, 5, 2, 2, 6, 6 }출력
5
동작 원리 설명
위 예제에서 6은 3번, 2는 3번, 5는 1번 나타납니다. 각 비트 위치별로 1의 개수를 세면, 6과 2가 기여하는 부분은 항상 3의 배수가 되어 m으로 나눌 때 0이 됩니다. 반면 5가 가진 비트는 나머지 계산에서 1로 남게 되어, 최종 결과값에 정확히 반영됩니다. 이처럼 비트 단위 카운팅 기법은 해시 맵 없이도 고유 요소를 선형 시간에 가깝게 찾아낼 수 있는 강력한 방법입니다.