CS 공부 & 면접 대비 0x05 [자료구조] : 배열에서 중복된 정수 찾기

배열에서 중복된 정수 찾기: 수학적 접근과 비트마스크 활용

---

질문

1부터 100까지의 정수가 들어있는 배열에서 한 개의 정수가 중복되었다. 어떻게 찾을 수 있을까요?

---

답변

중복된 정수를 찾는 방법으로 다음 두 가지를 사용할 수 있습니다:

1. 합의 차이 계산 (수학적 접근법)
2. 비트마스크를 이용한 중복 체크 (효율적인 메모리 사용)

방법 1: 합의 차이 계산

• 1부터 100까지의 정수의 합은 공식 n(n+1)/2로 구할 수 있습니다.
• 배열의 모든 값을 더한 합에서 이 이론적인 합을 빼면 중복된 정수를 찾을 수 있습니다.

방법 2: 비트마스크 사용 (n이 매우 클 경우)

• 배열의 각 수를 이진수로 변환한 후, 각 비트를 기록하는 방식입니다.
• 각 비트가 한 번만 등장해야 하므로, 이미 등장한 수를 감지할 수 있습니다.

---

질문과 답변에 대한 설명

방법 1: 수학적 접근법 – 합의 차이 이용

이 방법은 중복이 한 개만 존재할 때 사용 가능합니다.

원리 설명:

• 1부터 100까지의 합을 구하는 공식: S=n(n+1) / 2 ​
• 예를 들어, 1부터 5까지의 합은: S=5(5+1) / 2 = 15
• 배열 [1, 2, 3, 4, 4, 5]의 실제 합은 19입니다.
• 19 - 15 = 4 → 중복된 정수는 4입니다.

Python 코드 예시:

def find_duplicate(arr):
    n = len(arr) - 1
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(arr)
    return actual_sum - expected_sum

arr = [1, 2, 3, 4, 4, 5]
print("중복된 수:", find_duplicate(arr))  # Output: 중복된 수: 4

 

시간 및 공간 복잡도:

• 시간 복잡도: O(n) – 한 번의 순회
• 공간 복잡도: O(1) – 추가 메모리 사용 없음

---

방법 2: 비트마스크 활용 (n이 매우 큰 경우)

n이 매우 커져서 배열의 크기가 메모리에 영향을 미칠 경우, 비트마스크를 사용할 수 있습니다.

원리 설명:

• 각 정수를 비트로 표현하고, 등장 여부를 기록합니다.
• 이미 등장한 비트를 다시 발견하면 중복임을 감지할 수 있습니다.

Python 코드 예시 (비트마스크):

def find_duplicate_bitmask(arr):
    bitmask = 0
    for num in arr:
        bit_check = 1 << num
        if bitmask & bit_check:  # 이미 해당 비트가 1인 경우
            return num
        bitmask |= bit_check  # 해당 비트 켜기
    return -1  # 중복이 없는 경우

arr = [1, 2, 3, 4, 4, 5]
print("중복된 수:", find_duplicate_bitmask(arr))  # Output: 중복된 수: 4

 

비트 연산 이해

• bitmask & bit_check: 특정 비트가 이미 1인지 검사
• bitmask |= bit_check: 해당 비트를 1로 설정
• 1 << num: 특정 비트 위치로 이동 (예: 1 << 3 → 0b1000)

 

시간 및 공간 복잡도:

• 시간 복잡도: O(n) – 한 번의 순회
• 공간 복잡도: O(1) – 비트 마스크를 사용하는 메모리만 필요

---

비교표: 수학적 접근법 vs 비트마스크 접근법

구분수학적 접근법비트마스크 접근법

적합한 경우	중복이 1개, 범위가 작은 경우	중복이 1개, 범위가 매우 큰 경우
시간 복잡도	O(n)	O(n)
공간 복잡도	O(1)	O(1) (비트 마스크 사용)
구현 난이도	쉬움	중간
정확성	중복 1개인 경우만 가능	중복 1개인 경우만 가능

---

결론

중복된 정수를 찾는 방법은 문제의 크기와 조건에 따라 달라집니다.

• 수학적 접근법: 범위가 작고 중복이 1개일 경우.
• 비트마스크: 범위가 매우 크고 메모리 절약이 필요할 경우.

이 두 가지 방법 모두 **O(n)**의 시간 복잡도를 제공하면서도, 메모리를 최소화할 수 있습니다.

문제의 크기와 성질에 맞는 최적의 해결책을 선택하는 것이 중요