문제 소개
크기가 N인 숫자 배열이 있다고 가정해 봅시다. 이 배열의 모든 요소는 정확히 m번씩 등장하지만, 단 하나의 요소만 다른 횟수로 나타납니다. 우리의 목표는 바로 그 특별한 요소를 찾아내는 것입니다.
예를 들어, 배열 A = [6, 2, 7, 2, 2, 6, 6]이고 m = 3이라면, 대부분의 요소(6과 2)는 세 번씩 등장하지만 7은 한 번만 등장합니다. 따라서 출력 결과는 7이 됩니다.
해결 접근 방식: 비트 단위 카운팅
이 문제는 각 비트 위치별로 1이 등장하는 횟수를 세는 비트 연산 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 정수형 변수 하나의 전체 비트 크기를 계산합니다. (INT_SIZE = 8 × sizeof(int))
- INT_SIZE 크기의 카운트 배열(count)을 만들고 모든 값을 0으로 초기화합니다.
- 각 비트 위치 i에 대해 배열의 모든 요소 j를 검사하며, 해당 비트가 설정되어 있는지 확인합니다. (arr[j] AND 2^i ≠ 0)
- 비트가 설정되어 있다면 count[i]를 1 증가시킵니다.
- 마지막으로 res = Σ (count[i] mod m) × 2^i 공식을 통해 결과값을 계산합니다.
m번 반복되는 요소들은 각 비트에서 m의 배수만큼 기여하기 때문에, count[i]를 m으로 나눈 나머지는 오직 빈도가 다른 그 요소의 비트만 남게 됩니다. 이것이 이 알고리즘의 핵심 원리입니다.
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));
// 각 비트 위치별로 1의 개수를 셉니다
for(int i = 0; i < INT_SIZE; i++)
for(int j = 0; j < size; j++)
if((arr[j] & (1 << i)) != 0)
count[i] += 1;
// m으로 나눈 나머지를 이용해 결과 조합
unsigned res = 0;
for(int i = 0; i < INT_SIZE; i++)
res += (count[i] % m) * (1 << i);
return res;
}
int 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
동작 원리 상세 분석
위 예제에서 m = 3이고, 배열은 { 6, 2, 5, 2, 2, 6, 6 }입니다. 요소 6(이진수: 110)과 2(이진수: 010)는 각각 세 번 등장하고, 5(이진수: 101)는 한 번만 등장합니다.
- 비트 0 위치: 6, 5 → 1이 두 번 등장 → 2 % 3 = 2 → 해당 비트 기여
- 비트 1 위치: 6, 2, 2, 6, 2, 6 → 1이 여섯 번 등장 → 6 % 3 = 0 → 기여 없음
- 비트 2 위치: 6, 5, 6, 6 → 1이 네 번 등장 → 4 % 3 = 1 → 해당 비트 기여
최종적으로 비트 0과 비트 2가 설정된 값, 즉 101₂ = 5가 결과로 반환됩니다.
시간 및 공간 복잡도
- 시간 복잡도: O(N × INT_SIZE) — 배열의 각 요소에 대해 정수 비트 수만큼 검사합니다.
- 공간 복잡도: O(INT_SIZE) — 비트 크기만큼의 카운트 배열이 필요합니다.
해시 맵을 사용하는 방법보다 추가 메모리 사용량이 일정하게 유지된다는 점에서, 이 비트 연산 기법은 메모리 제약이 있는 환경에서 특히 유용합니다.