Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 세는 유효한 삼각형의 개수: 정렬과 두 포인터 활용법

문제 설명

음수가 아닌 정수들로 이루어진 배열이 주어졌을 때, 배열에서 세 개의 값을 골라 삼각형의 세 변의 길이로 사용할 수 있는 조합(트리플렛)의 개수를 구하는 것이 목표입니다.

예를 들어 입력이 [2, 2, 3, 4]라면 결과는 3이 됩니다. 첫 번째 2를 사용한 [2, 3, 4], 두 번째 2를 사용한 [2, 3, 4], 그리고 [2, 2, 3]으로 각각 삼각형을 만들 수 있기 때문입니다.

접근 방법

삼각형이 성립하려면 가장 긴 변의 길이가 나머지 두 변의 합보다 작아야 한다는 삼각 부등식이 반드시 만족되어야 합니다. 이 성질을 활용하면 세 변을 모두 비교하지 않고도 조건을 판단할 수 있습니다.

알고리즘은 다음과 같은 단계로 진행됩니다.

  • ret := 0으로 초기화하고, n := nums의 크기로 설정한 뒤 nums를 오름차순으로 정렬합니다.
  • i를 n − 1부터 0까지 역순으로 순회하며 nums[i]를 가장 긴 변으로 고정합니다.
    • right := i − 1, left := 0으로 두 포인터를 설정합니다.
    • left < right인 동안 다음을 반복합니다.
      • sum := nums[left] + nums[right]
      • sum > nums[i]이면, left부터 right−1까지의 모든 값과 nums[right]의 합이 nums[i]보다 크므로 ret에 right − left를 더하고 right를 1 감소시킵니다.
      • 그렇지 않으면 left를 1 증가시켜 합을 키웁니다.
  • 모든 순회가 끝나면 ret을 반환합니다.

배열을 미리 정렬해 두었기 때문에, 두 포인터 기법으로 각 가장 긴 변에 대해 O(n) 시간 안에 가능한 조합을 모두 찾을 수 있습니다. 전체 시간 복잡도는 정렬을 포함해 O(n²)입니다.

C++ 구현 예제

아래 코드를 통해 동작 방식을 더 자세히 이해할 수 있습니다.

#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