본문 바로가기

코테

[Codility] CountTriangles c++

반응형

처음에는 n^3방법을 썼다가

sort하면 조금 더 줄일 수 있다는 것을 알았다

#include <algorithm>

int answer = 0;

int solution(vector<int> &A) {
    sort(A.begin(), A.end());
    for(int i=0; i<A.size(); i++){
        int k=i+2;
        for(int j=i+1; j<A.size(); j++){
            while(k<A.size() && A[i]+A[j]>A[k]){
                k++;
            }
            if(k>j) answer+= k-j-1;
        }
    }
    return answer;
}
반응형

'코테' 카테고리의 다른 글

[HackerRank] Draw The Triangle 1,2  (0) 2022.05.17
[HarckerRank] Top Earners  (0) 2022.05.13
[Programmers] 배달 python  (0) 2022.02.09
[Programmers] 숫자 게임 python  (0) 2022.02.09
[Programmers] 네트워크 python  (0) 2022.02.08