숫자 배열이 주어졌을 때, 배열에서 세 개의 숫자를 골라 삼각형의 세 변의 길이로 사용할 수 있는 조합(트리플렛)의 개수를 구하는 문제입니다.
예를 들어 입력이 [2,2,3,4]라면 결과는 3이 됩니다. 첫 번째 2를 사용한 [2,3,4], 두 번째 2를 사용한 [2,3,4], 그리고 [2,2,3]으로 총 세 가지 조합이 유효한 삼각형을 만들 수 있기 때문입니다.
접근 방법
삼각형이 성립하려면 가장 긴 변이 나머지 두 변의 합보다 작아야 한다는 삼각형 부등식을 활용합니다. 이를 효율적으로 확인하기 위해 다음 단계를 따릅니다.
- 결과값 ret을 0으로 초기화하고, n은 배열의 크기로 설정한 뒤 배열을 오름차순으로 정렬합니다.
- i를 n-1부터 0까지 역순으로 순회하며, i번째 요소를 삼각형의 가장 긴 변으로 간주합니다.
- right는 i-1, left는 0으로 초기화합니다.
- left가 right보다 작은 동안 다음을 반복합니다.
- sum = nums[left] + nums[right]를 계산합니다.
- sum이 nums[i]보다 크면, left부터 right 사이의 모든 값과 nums[right]의 합도 nums[i]보다 크므로 ret에 (right - left)를 더하고 right를 1 감소시킵니다.
- 그렇지 않으면 left를 1 증가시킵니다.
- 모든 순회가 끝나면 ret을 반환합니다.
이 방식은 정렬에 O(n log n), 투 포인터 탐색에 O(n²)이 소요되어 전체 시간 복잡도는 O(n²)입니다. 브루트 포스 방식의 O(n³)보다 훨씬 효율적입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int ret = 0;
int n = nums.size();
sort(nums.begin(), nums.end());
for(int i = n - 1; i >= 0; i--){
int right = i - 1;
int left = 0;
while(left < right){
int sum = nums[left] + nums[right];
if(sum > nums[i]){
ret += right - left;
right--;
}else left++;
}
}
return ret;
}
};
main(){
vector<int> v = {2,2,3,4};
Solution ob;
cout << (ob.triangleNumber(v));
}입력
[2,2,3,4]
출력
3