문제 설명
n개의 정수로 이루어진 배열 nums와 목표값 target이 주어졌을 때, 조건 nums[i] + nums[j] + nums[k] < target을 만족하는 인덱스 삼중쌍 (i, j, k)의 개수를 구하는 것이 이번 문제의 목표입니다. 여기서 i, j, k는 모두 0부터 n-1 사이의 범위에 속합니다.
예를 들어 입력이 nums = [-2, 0, 1, 3]이고 target = 2라면 출력은 2가 됩니다. 합이 2보다 작은 삼중쌍이 [-2, 0, 1]과 [-2, 0, 3] 두 개뿐이기 때문입니다.
접근 방법: 정렬 + 투 포인터
모든 삼중쌍을 하나씩 확인하는 브루트 포스 방식은 O(n³)의 시간이 걸려 비효율적입니다. 대신 배열을 먼저 정렬한 뒤 투 포인터(Two Pointers) 기법을 적용하면 O(n²) 시간 안에 해결할 수 있습니다.
알고리즘의 진행 순서는 다음과 같습니다.
- 결괏값
ret을 0으로 초기화합니다. - 배열을 오름차순으로 정렬합니다.
- 배열의 크기를
n에 저장합니다. - 첫 번째 원소
i를 0부터 n-3까지 고정하면서 다음을 반복합니다.left = i + 1,right = n - 1로 설정합니다.left < right인 동안 세 수의 합sum을 계산합니다.sum < target이면ret += right - left를 더하고left를 증가시킵니다.- 그렇지 않으면
right를 감소시킵니다.
- 모든 반복이 끝나면
ret을 반환합니다.
핵심 아이디어: 배열이 정렬되어 있으므로, a[i] + a[left] + a[right] < target이라면 left부터 right - 1 사이의 어떤 값과 조합해도 조건을 만족합니다. 따라서 한 번의 비교로 (right - left)개의 유효한 삼중쌍을 동시에 셀 수 있어 탐색 범위를 크게 줄일 수 있습니다.
C++ 코드 구현
아래 코드를 통해 실제 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int threeSumSmaller(vector<int>& a, int t) {
int ret = 0;
sort(a.begin(), a.end());
int n = a.size();
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = a[i] + a[left] + a[right];
if (sum < t) {
ret += right - left;
left++;
} else {
right--;
}
}
}
return ret;
}
};
int main() {
Solution ob;
vector<int> v = {-2, 0, 1, 3};
cout << (ob.threeSumSmaller(v, 2));
}실행 결과
입력:
[-2,0,1,3] 2
출력:
2
복잡도 분석
- 시간 복잡도: O(n²) — 정렬에 O(n log n)이 소요되고, 이후 각 고정 인덱스
i마다 투 포인터 탐색이 O(n)으로 진행됩니다. - 공간 복잡도: O(1) — 추가적인 자료구조 없이 포인터 변수만 사용하므로 상수 공간으로 해결됩니다.