C++ 비트 배열(Bit Array)로 배열의 중복 요소 찾기

개념

n개의 숫자로 이루어진 배열이 있으며, 여기서 n은 최대 32,000입니다. 이 배열에는 중복된 값이 포함되어 있을 수 있지만, n의 정확한 값은 알 수 없습니다. 문제는 단 4킬로바이트(KB)의 메모리만 사용할 수 있는 상황에서 배열에 존재하는 모든 중복 요소를 어떻게 찾아 출력하느냐는 것입니다.

입력 및 출력 예시

예시 1

입력:

arr[] = {2, 6, 2, 11, 13, 11}

출력:

2 11

배열에서 2와 11은 한 번씩 더 등장하는 중복 요소입니다.

예시 2

입력:

arr[] = {60, 50, 60}

출력:

접근 방법

사용 가능한 메모리가 4KB라는 것은 최대 8 × 4 × 2¹⁰, 즉 약 32,768비트를 다룰 수 있다는 의미입니다. 32 × 2¹⁰비트는 32,000보다 크므로, 각 비트가 하나의 정수를 대표하는 32,000비트 크기의 비트 벡터(bit vector)를 만드는 것이 가능합니다.

만약 32,000개보다 많은 비트가 필요하더라도 손쉽게 확장할 수 있습니다. 이렇게 구현한 비트 벡터를 이용해 배열을 처음부터 끝까지 순회하면서, 각 요소 v를 만날 때마다 v번째 비트를 1로 설정해 '등장했음'을 표시합니다. 순회 도중 이미 비트가 1로 설정되어 있는 요소를 만나면, 그것이 곧 중복 요소이므로 화면에 출력하면 됩니다.

이 방식의 시간 복잡도는 O(n)이며, 공간 복잡도는 약 4KB로 매우 효율적입니다.

구현 예제

// C++ 프로그램: 배열의 모든 중복 요소 출력하기
#include <bits/stdc++.h>
using namespace std;

// 정수 배열을 이용해 비트 배열을 표현하는 클래스
class BitArray{
   int *arr1;
   public:
   BitArray() {}
   // 생성자
   BitArray(int n1){
      // 32로 나눈 값 사용. n비트를 저장하려면
      // n/32 + 1개의 정수가 필요함 (int를 32비트로 가정)
      arr1 = new int[(n1 >> 5) + 1];
   }
   // 주어진 위치의 비트 값 조회
   bool get(int pos1){
      // 32로 나눠 해당 정수의 인덱스를 찾음
      int index1 = (pos1 >> 5);
      // arr1[index] 안에서의 비트 번호 결정
      int bitNo1 = (pos1 & 0x1F);
      // 해당 비트의 값 반환
      return (arr1[index1] & (1 << bitNo1)) != 0;
   }
   // 주어진 위치에 비트 설정
   void set(int pos1){
      // 비트 위치의 인덱스 계산
      int index1 = (pos1 >> 5);
      // arr1[index1]에 해당 비트 설정
      int bitNo1 = (pos1 & 0x1F);
      arr1[index1] |= (1 << bitNo1);
   }
   // 모든 중복 요소를 출력하는 함수
   void checkDuplicates1(int arr1[], int n1){
      // 32000비트 크기의 비트 배열 생성
      BitArray ba1 = BitArray(320000);
      // 배열 요소를 순회
      for (int i = 0; i < n1; i++){
         // 비트 배열에서의 인덱스
         int num1 = arr1[i];
         // num이 이미 비트 배열에 존재하면 출력
         if (ba1.get(num1))
            cout << num1 << " ";
         // 그렇지 않으면 비트 배열에 삽입
         else
            ba1.set(num1);
      }
   }
};
// 드라이버 코드
int main(){
   int arr1[] = {2, 6, 2, 11, 13, 11};
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   BitArray obj1 = BitArray();
   obj1.checkDuplicates1(arr1, n1);
   return 0;
}

실행 결과

2 11

정리

이 기법의 핵심은 비트 연산(>>, &, |)을 활용해 하나의 int(32비트)에 32개의 불리언 정보를 압축 저장한다는 점입니다. (pos >> 5)는 32로 나누는 것과 동일하고, (pos & 0x1F)는 31로 나눈 나머지와 같으므로 빠르게 인덱스와 비트 위치를 계산할 수 있습니다. 해시 셋(hash set)을 사용하지 않고도 극도로 제한된 메모리 환경에서 중복 검출 문제를 해결할 수 있는 대표적인 비트맵(bitmap) 활용 사례입니다.

C++ 비트 배열(Bit Array)로 배열의 중복 요소 찾기 — 4KB 메모리 제약 문제 풀이