문제 개요
다음 두 가지 메서드를 갖춘 자료구조를 설계한다고 가정해 보겠습니다.
- add(val) — 값 val을 자료구조에 추가합니다.
- find(val) — 합이 val이 되는 두 원소가 존재하는지 확인합니다.
핵심 요구 사항은 쿼리가 들어올 때마다 매번 전체 데이터를 검색하지 않고도 즉시 결과를 얻을 수 있도록 설계하는 것입니다.
예를 들어 객체 obj를 생성한 뒤 6, 14, 3, 8, 11, 15를 차례로 추가하고, 이어서 obj.find(9), obj.find(11), obj.find(15)를 호출하면 출력은 True, True, False가 됩니다. 9는 6+3으로, 11은 3+8로 만들 수 있습니다. 반면 15는 자료구조에 포함되어 있더라도 두 수의 합이 15가 되는 조합은 없습니다.
해결 접근 방법
이 문제는 두 개의 집합(set)을 활용해 다음과 같이 해결할 수 있습니다.
- 생성자 정의 — nums(새로운 집합)와 multiple(새로운 집합)을 초기화합니다.
- add() 함수 정의 — val이 이미 nums에 존재하면 multiple에 val을 추가하고, 그렇지 않으면 nums에 val을 추가합니다.
- find() 함수 정의 — nums의 각 원소 n에 대해 아래 조건을 검사합니다.
- n + n이 val과 같으면, n이 multiple에 존재하는 경우에만 True를 반환합니다. (같은 수를 두 번 더하는 경우는 해당 값이 중복으로 등장했을 때만 가능하기 때문입니다.)
- 그렇지 않고 val − n이 nums에 존재하면 True를 반환합니다.
- 모든 검사 후에도 조건을 만족하지 못하면 False를 반환합니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class PairSumChecker:
def __init__(self):
self.nums = set()
self.multiple = set()
def add(self, val):
if val in self.nums:
self.multiple.add(val)
else:
self.nums.add(val)
def find(self, val):
for n in self.nums:
if n + n == val:
return n in self.multiple
elif val - n in self.nums:
return True
return False
obj = PairSumChecker()
obj.add(6)
obj.add(14)
obj.add(3)
obj.add(8)
obj.add(11)
obj.add(15)
print(obj.find(9))
print(obj.find(11))
print(obj.find(15))
입력
print(obj.find(9)) print(obj.find(11)) print(obj.find(15))
출력
True True False
동작 원리 정리
nums 집합은 지금까지 한 번이라도 등장한 고유한 값을 저장하고, multiple 집합은 두 번 이상 등장한 값을 저장합니다. 덕분에 find()에서 "같은 수를 두 번 더하는 경우(n + n == val)"도 해당 값이 실제로 중복 존재할 때만 성립하도록 정확하게 판별할 수 있습니다. 집합의 탐색과 삽입은 평균적으로 O(1) 시간에 처리되므로, 데이터가 많아져도 빠른 응답 속도를 유지할 수 있다는 점이 이 설계의 가장 큰 장점입니다.