본문 바로가기
Codility

[Codility] Caterpillar method : CountTriangles

by paysmile 2021. 7. 16.

https://app.codility.com/programmers/lessons/15-caterpillar_method/count_triangles/

 

CountTriangles coding task - Learn to Code - Codility

Count the number of triangles that can be built from a given set of edges.

app.codility.com

#include<algorithm>
// 1 2 5 8 10 12
int solution(vector<int> &A) {
    sort(A.begin(),A.end());
    int sz = A.size();
    int answer = 0;
    
    for(int i=0; i<sz-2; i++){
        int k = i +2;
        for(int j = i+1; j<sz; j++){
            while(k <sz && A[i] + A[j] > A[k]){
                k+=1;
            }
            if (k > j)
                answer += k - j - 1;
        }
    }
    return answer;
}