파이썬 비트 배열(Bit Array)로 배열의 중복 요소 찾기: 4KB 메모리 제약 문제

문제 소개

서로 다른 n개의 숫자로 이루어진 배열이 있다고 가정해 보겠습니다. n은 최대 32,000까지 가능하고, 배열에는 중복된 값이 존재할 수 있으며 n의 실제 크기는 미리 알 수 없습니다. 이때 사용할 수 있는 메모리가 단 4킬로바이트(KB)뿐이라면, 어떻게 해야 배열 안의 모든 중복 값을 찾아낼 수 있을까요?

예를 들어 입력이 [2, 6, 2, 11, 13, 11]이라면, 2와 11이 각각 두 번씩 등장하므로 출력은 [2, 11]이 됩니다.

접근 방법: 비트 배열(Bit Array)

핵심 아이디어는 각 숫자를 비트 1개에 대응시키는 것입니다. 4KB는 4 × 1024 × 8 = 32,768비트이므로, 0~32,000 범위의 숫자를 각각 비트 하나로 표현하기에 충분합니다. 숫자가 처음 등장하면 해당 위치의 비트를 1로 설정하고, 이후 같은 숫자가 다시 나타나면 이미 비트가 1로 되어 있으므로 중복으로 판단할 수 있습니다.

이를 위해 다음과 같은 단계로 진행합니다.

비트 배열 형태의 데이터 구조 bit_arr를 정의합니다.
생성자(__init__): 크기 n을 받아 길이가 (n >> 5) + 1인 정수 배열을 만들고 0으로 초기화합니다. 정수 하나당 32비트를 저장할 수 있습니다.
get_val(pos): pos번째 비트가 설정되어 있는지 확인합니다.
index := pos >> 5
bitNo := pos & 31
arr[index] & (1 << bitNo)의 결과가 0이 아니면 True를 반환합니다.
set_val(pos): pos번째 비트를 1로 설정합니다.
index := pos >> 5
bitNo := pos & 31
arr[index] |= (1 << bitNo)

메인 로직

bit_arr(32000) 객체를 생성합니다.
입력 배열을 처음부터 끝까지 순회하면서 각 숫자 num에 대해 검사합니다.
get_val(num)이 참이면 num을 출력합니다(중복 발견).
그렇지 않으면 set_val(num)을 호출해 해당 비트를 1로 만듭니다.

파이썬 구현 예제

아래 코드를 통해 동작 방식을 더 자세히 살펴보겠습니다.

class bit_arr:
    def __init__(self, n):
        self.arr = [0] * ((n >> 5) + 1)

    def get_val(self, pos):
        self.index = pos >> 5
        self.bitNo = pos & 31
        return (self.arr[self.index] & (1 << self.bitNo)) != 0

    def set_val(self, pos):
        self.index = pos >> 5
        self.bitNo = pos & 31
        self.arr[self.index] |= (1 << self.bitNo)


def find_duplicates(arr):
    bit_set = bit_arr(32000)
    for i in range(len(arr)):
        num = arr[i]
        if bit_set.get_val(num):
            print(num, end=" ")
        else:
            bit_set.set_val(num)


arr = [2, 6, 2, 11, 13, 11]
find_duplicates(arr)

입력

[2, 6, 2, 11, 13, 11]

출력

2 11

동작 원리 정리

pos >> 5는 pos를 32로 나눈 몫과 같으므로 해당 숫자가 저장될 정수 슬롯의 인덱스를 의미하고, pos & 31은 32로 나눈 나머지와 같으므로 그 슬롯 안에서의 비트 위치를 나타냅니다. 이처럼 비트 연산만으로 인덱스를 계산하면 별도의 해시 테이블 없이도 O(n) 시간에 중복을 찾을 수 있으며, 전체 메모리 사용량도 약 4KB로 제한됩니다.