숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, min(S) + max(S) ≤ k 조건을 만족하는 공집합이 아닌 부분 집합 S의 개수를 구하는 문제입니다.
여기서 주의할 점은 부분 집합이 멀티셋(multiset)처럼 취급된다는 것입니다. 부분 집합은 '값'이 아니라 리스트의 특정 요소(인덱스)를 기준으로 선택되기 때문에, 값이 같더라도 서로 다른 요소라면 별개의 부분 집합으로 계산됩니다.
예시
입력이 nums = [2, 2, 5, 6], k = 7이라면 정답은 6이며, 만들 수 있는 부분 집합은 다음과 같습니다.
- [2]
- [2]
- [2, 2]
- [2, 5]
- [2, 5]
- [2, 2, 5]
접근 방법: 정렬 + 투 포인터(Two Pointer)
모든 부분 집합을 일일이 생성하면 지수적으로 경우의 수가 늘어나므로 비효율적입니다. 대신 리스트를 정렬한 뒤 투 포인터 기법을 사용하면 선형 시간 안에 개수를 셀 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 리스트를 오름차순으로 정렬합니다.
- 각 인덱스 i에 대해 A[i]를 부분 집합의 최솟값으로 고정합니다.
- A[i] + A[j] ≤ K를 만족하는 가장 큰 인덱스 j를 찾습니다. i가 커질수록 A[i]도 커지므로 j는 단조 감소하며, 매번 처음부터 찾을 필요 없이 이전 위치에서 줄여 나가면 됩니다.
- 최솟값 A[i]를 포함하고 나머지 요소를 인덱스 i+1 ~ j 범위에서 임의로 선택하면 조건을 만족하는 부분 집합이 되므로, 경우의 수는 2^(j − i)입니다(요소 하나만으로 이루어진 [A[i]]도 포함).
알고리즘 단계를 정리하면 다음과 같습니다.
- N := 리스트 A의 크기
- 리스트 A를 정렬
- ans := 0, j := N − 1
- i를 0부터 N−1까지 반복:
- A[i] + A[j] > K인 동안 j를 1씩 감소
- i ≤ j이고 A[i] + A[j] ≤ K이면 ans += 2^(j − i)
- ans 반환
구현 예제
class Solution:
def solve(self, A, K):
N = len(A)
A.sort()
ans = 0
j = N - 1
for i in range(N):
# 조건을 만족할 때까지 오른쪽 포인터 j를 이동
while j and A[i] + A[j] > K:
j -= 1
# 유효한 범위일 때만 경우의 수 누적
if i <= j and A[i] + A[j] <= K:
ans += 1 << (j - i)
return ans
ob = Solution()
nums = [2, 2, 5, 6]
k = 7
print(ob.solve(nums, k))
입력
[2, 2, 5, 6]
출력
6
복잡도 분석
정렬에 O(N log N), 투 포인터 탐색에 O(N)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다. 추가 메모리 사용량은 상수 수준으로 O(1)입니다. 브루트포스 방식으로 모든 부분 집합을 검사하는 O(2^N) 접근과 비교하면 훨씬 효율적입니다.