문제 설명
숫자로 이루어진 리스트 nums와 하나의 값 target이 주어졌을 때, 인덱스가 i < j < k를 만족하면서 아래 조건을 충족하는 트리플릿(세 원소 조합)의 개수를 구하는 것이 목표입니다.
nums[i] + nums[j] + nums[k] < target
예를 들어 nums = [-2, 6, 4, 3, 8], target = 12가 입력으로 주어지면 출력은 5가 됩니다. 조건을 만족하는 트리플릿은 다음과 같습니다.
- [-2, 6, 4]
- [-2, 6, 3]
- [-2, 4, 3]
- [-2, 4, 8]
- [-2, 3, 8]
해결 접근 방법: 정렬 + 투 포인터
모든 조합을 일일이 확인하는 브루트 포스 방식은 O(n³)의 시간이 걸리지만, 정렬과 투 포인터(Two Pointer) 기법을 활용하면 O(n²) 시간 안에 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 먼저 리스트를 오름차순으로 정렬한 뒤 첫 번째 원소 i를 고정하고, 나머지 두 원소 j와 k를 양쪽 끝에서부터 좁혀가며 탐색합니다. 세 수의 합이 target 이상이면 k를 왼쪽으로 이동시켜 합을 줄이고, 조건을 만족하면 j와 k 사이의 모든 원소를 세 번째 값으로 선택할 수 있으므로 한 번에 (k - j)개씩 개수를 더할 수 있습니다.
알고리즘 단계
- 리스트 nums를 오름차순으로 정렬합니다.
- 정답 변수 ans를 0으로 초기화하고, n은 리스트의 크기로 설정합니다.
- i를 0부터 n-1까지 순회하며, 매번 k := n - 1로 초기화합니다.
- j를 i+1부터 n-1까지 순회합니다.
- k > j이면서 nums[i] + nums[j] + nums[k] >= target인 동안 k를 1씩 감소시킵니다.
- j == k가 되면 내부 반복문을 종료합니다.
- 그렇지 않으면 ans에 (k - j)를 더합니다. 이는 j+1부터 k까지의 원소를 세 번째 값으로 고르는 경우의 수입니다.
- 모든 순회가 끝나면 ans를 반환합니다.
구현 코드
class Solution:
def solve(self, nums, target):
nums.sort()
ans = 0
n = len(nums)
for i in range(n):
k = n - 1
for j in range(i + 1, n):
while k > j and nums[i] + nums[k] + nums[j] >= target:
k -= 1
if j == k:
break
ans += k - j
return ans
ob1 = Solution()
nums = [-2, 6, 4, 3, 8]
target = 12
print(ob1.solve(nums, target))입력
[-2, 6, 4, 3, 8], 12
출력
5
복잡도 분석
시간 복잡도: O(n²) — 바깥쪽 반복문이 n번 실행되고, 각 단계에서 두 포인터 j와 k가 전체적으로 최대 n번 이동합니다.
공간 복잡도: O(1) — 정렬에 필요한 공간을 제외하면 포인터 변수 몇 개만 사용하므로 추가 메모리가 거의 없습니다.