정수 배열 nums가 주어졌을 때, 배열에 있는 value가 한 번 이상 나오면 true, 아니라면 false 반환
문제 파악
정수 배열에서 중복된 값이 있는 지 확인하기.
중복된 값이 있다면 False, 중복된 값이 없다면 True
문제 정의
지금까지 본 값들의 집합을 유지하면서, 새로운 값이 이미 존재하는지 빠르게 판단
문제의 핵심
Dynamic Set(동적 집합)을 유지하면서 Membership Query를 반복 수행.
Membership Query - 어떤 원소 x가 현재 집합(set)에 들어가 잇는가? 를 묻는 질의
- 계산이론(Theory of Computation) 에서
언어 𝐿에 대해 x ∈ L ? 를 묻는 것을 membership problem / membership query 라고 부름
"이 문자열이 이 언어에 속하냐? 라는 질문
자료 구조 쪽으로 내려오면서 의미가 확장되어 x ∈ S ?
"이 문자열이 원소에 속하냐?"
계산 이론에서 시작된 정식 용어로 어떤 원소가 특정 집합에 속하는지 묻는 질문
사고 흐름
(1) 필요한 연산 insert(x), 값이 존재하는지 확인 contain(x)
(2) 이러한 연산을 잘 지원하는 ADT 떠올리기
- List :
insert - O(1),contains - O(n) - Sorted List :
insert - O(n),contains - O(log n) - Set :
insert - O(1),contains - O(1) - Tree Set :
insert - O(log n),contains - O(log n) - Bitset :
insert - O(1),contains - O(1)
-> 중복 탐지 문제에서는 Set ADT가 가장 자연스럽게 떠올라야 함
(3) ADT -> 구현체 매핑
python -> set(hash table)
(4) 구현
구현 과정
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
tmp = set(nums)
return False if len(nums)==len(tmp) else True
set ADT를 사용했지만 모든 len(nums)로 모든 insert후 상태를 검사함
시간 복잡도 O(n), 공간복잡도 O(n)
개선 방안
elary exit
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
seen = set()
for n in nums:
if n in seen:
return True
seen.add(n)
return False
seen + early exit을 사용해서 insert / contains를 순차적으로 사용해서, 중복을 발견하는 즉시 종료할 수 있음
시간복잡도, 공간복잡도 O(n) 으로 최악의 겨우는 같지만 평균 실행 시간은 더 빠를 수 있음
공간을 줄일 수 있는 방법?
class Solution:
def hasDuplicate(self, nums:List[int]) -> bool:
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
return True
return False조건이 허락된다면 정렬을 사용.
시간복잡도는 O(nlogn), 공간복잡도는 O(1) (in-place sort)
-> 여기서는 공간을 줄이는 대신에 시간을 희생함.
질문
Q. 왜 set을 쓰면 중복을 찾을 수 있는지?
A. 해시 테이블 기반이므로, set은 중복을 허용하지 않는 자료 구조.
내부적으로 hash 값을 사용하여 저장한다. 평균 삽입과 조회 모두 O(1)
Q. set을 쓰는 방식의 단점
A. 추가 메모리를 사용하게 됨 O(n)
이론적으로는 해시 충돌 발생 가능성도 있음.
Q. 공간 복잡도를 O(1)로 줄이는 방법
A. 정렬을 사용함. 그러나 시간복잡도가 O(n log n)으로 증가.
원본 배열 변경 가능성이 있다. Trade-off 관계
Q. 숫자의 범위가 제한되어 있다면?
예를 들어 0 ≤ nums[i] ≤ 10^5 라면?
A. Boolean 배열 / Bitset 사용 가능
그 경우 공간복잡도 O(range) 시간 복잡도 O(n)
Q. streaming 데이터라면?
A. 전체 배열을 메모리에 올릴 수 없음. seen set 으로 한 개씩 처리. 혹은 Bloom Filter(확률적 자료구조)
추가
Streaming 데이터
- 데이터가 한 번에 주어지지 않고, 순차적으로 도착하는 Streaming 데이터(로그 스트림, 네트워크 패킷, 실시간 센서 데이터) 는 전체 배열을 메모리에 저장하기 어려움.
-> seen set 으로 처리 (한 개씩 처리하면서 이전 값만 기억, 입력이 끝날 때까지 계속)
seen = set()
def process(x):
if x in seeen:
print("duplicate detected")
else:
seen.add(x)그러나 seen set이 계속 커지면, 메모리 무한 증가 가능성이 있음
여기서 Bloom Filter 등장
Bloom Filter : 중복을 '확률적으로' 판별하는 메모리 효율적인 자료 구조
Streaming 데이터, 수억개의 값, Set으로는 메모리가 부족하다면
정확도의 일부를 희생하고 메모리를 절약한다.
Bloom Filter의 핵심 특징은
- False Positive 가능 -> 없는데 있다고 나올 수 있음
- False Negative 없음 -> 있다고 했으면 진짜 있음
- 메모리 매우 작음 -> bit array 사용
- 삭제 어려움 -> 기본형은 불가
즉, 값의 범위가 제한되어 있다면 해시 Set대신 값을 인덱스로 사용하는
Boolean Array나 Bitset을 사용할 수 있다.
Streaming 환경에서는 seen Set으로 중복을 즉시 탐지할 수 있지만
메모리가 제한된다면 Bloom Filter처럼 확률적 자료 구조를 고려할 수 있다.
