Lesson 6. Sorting - Triangle #2 (속도개선)

1. 속도개선 아이디어

문제에서 삼각형을 만드는 조건을 다음과 같이 제시하고 있다.

1. 0 ≤ P < Q < R < N
2. A[P] + A[Q] > A[R]
3. A[Q] + A[R] > A[P]
4. A[R] + A[P] > A[Q]

여기서 조건1은 삼각형을 만드는데 쓰이는 값(인덱스)이 중복 사용할 수 없다는 뜻이지,

Vector A의 값 순서가 지켜져야 한다는 뜻은 아니다.

 

따라서 Vector A를 오름차순으로 정렬하면, 확인해야 하는 경우의 수가 줄어든다.

왜냐하면 오름차순으로 정렬된 상태에서는 조건3과 조건4는 당연하기 때문이다.  (A[R] > A[P], A[Q])

 

즉, 우리가 확인해야 하는 경우는 오직 조건2 뿐이다.

조건2는 나란히 붙어있는 3개의 값을 확인하면 된다.

 

2. 코드 (C++)

#include <cstdint>
#include <algorithm>

int solution(vector<int> &A) {

    sort(A.begin(), A.end());

    if(A.size() < 3) return 0;

    for(size_t i = 0; i < A.size() - 2; i++)
    {
        int64_t P = A[i];
        int64_t Q = A[i+1];
        int64_t R = A[i+2];
        if(P + Q > R) return 1;
    }

    return 0;
}

 

3. 결과