배열 nums와 정수 k가 주어졌다고 가정해 봅시다. 이때 nums의 비어 있지 않은 모든 부분 수열(subsequence) 중에서, 그 수열 안의 최솟값과 최댓값의 합이 k 이하가 되는 경우의 수를 구하는 것이 목표입니다. 답이 매우 커질 수 있으므로 결과는 109 + 7로 나눈 나머지를 반환해야 합니다.
문제 이해하기
예를 들어 입력이 nums = [4, 6, 7, 8], k = 11이라면 출력은 4입니다. 조건을 만족하는 부분 수열은 다음과 같습니다.
[4] — 최솟값 4, 최댓값 4 → 4 + 4 ≤ 11 ✓
[4, 6] — 최솟값 4, 최댓값 6 → 4 + 6 ≤ 11 ✓
[4, 6, 7] — 최솟값 4, 최댓값 7 → 4 + 7 ≤ 11 ✓
[4, 7] — 최솟값 4, 최댓값 7 → 4 + 7 ≤ 11 ✓
접근 방법: 정렬 + 투 포인터
부분 수열의 성질을 활용하면 이 문제를 효율적으로 해결할 수 있습니다. 배열을 오름차순으로 정렬하면 어떤 부분 수열의 최솟값은 항상 왼쪽에, 최댓값은 항상 오른쪽에 위치하게 됩니다. 따라서 두 포인터를 사용해 각 원소가 '최솟값' 역할을 하는 경우의 수를 세면 됩니다.
핵심 아이디어는 다음과 같습니다. 만약 nums[left] + nums[right] ≤ k라면, 인덱스 left를 최솟값으로 포함하고 left와 right 사이의 원소들을 임의로 선택한 모든 부분 수열이 조건을 만족합니다. 사이에 있는 원소의 개수가 num_inside = right - left개이므로, 각 원소마다 '포함한다 / 포함하지 않는다'의 두 가지 선택지가 있어 총 2num_inside개의 부분 수열이 가능합니다.
알고리즘 단계
배열 nums를 오름차순으로 정렬합니다.
m := 10^9 + 7 (나머지 연산에 사용할 모듈러 값)
left := 0, right := len(nums) - 1, res := 0 으로 초기화합니다.
left ≤ right인 동안 다음을 반복합니다:
만약 nums[left] + nums[right] > k이면, right를 1 감소시킵니다. (두 값의 합이 너무 크므로 최댓값 후보를 줄임)
그렇지 않으면:
num_inside := right - left
res := (res + 2^num_inside) mod m
left를 1 증가시킵니다. (현재 left를 최솟값으로 하는 모든 경우를 이미 계산했기 때문)
res를 반환합니다.
파이썬 구현 예제
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
def solve(nums, k): nums.sort() m = 10**9 + 7 left = 0 right = len(nums) - 1 res = 0 while(left <= right): if nums[left] + nums[right] > k: right -= 1 else: num_inside = right - left res = (res + pow(2, num_inside, m)) % m left += 1 return res nums = [4,6,7,8] k = 11 print(solve(nums, k))
입력
[4,6,7,8], 11
출력
4
복잡도 분석
정렬에 O(n log n)의 시간이 소요되며, 투 포인터 탐색은 각 포인터가 최대 n번씩 이동하므로 O(n)입니다. 따라서 전체 시간 복잡도는 O(n log n)이고, 공간 복잡도는 정렬 방식에 따라 O(1) ~ O(n)입니다. 완전 탐색으로 모든 부분 수열을 확인하는 O(2^n) 방식과 비교하면 훨씬 효율적인 접근입니다.