Lesson6. Sorting - Triangle

Triangle - Determine whether a triangle can be built from a given set of edges.

https://app.codility.com/programmers/lessons/6-sorting/triangle/

문제요약

N개의 정수 배열 A의 triplet (P, Q, R)이 있을 때 0<=P<Q<R<N이고 A[P] + A[Q] > A[R], A[Q] + A[R] > A[P], A[R] + A[P] > A[Q]이면 triangular이다.

A에 triangular가 존재하면 1, 그렇지 않으면 0을 반환한다.

Assume that:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

임의의 세 수 A[P], A[Q], A[R]이 주어질 때 위 조건을 만족하는지 알아보기 위해 3가지 모두를 확인하지 않아도 된다. 3값 중 가장 큰 값 보다 나머지 두 값의 합이 더 큰지만 확인하면 되는데, 이유는 가장 큰 값이 더해지는 쪽으로 포함되면 당연히 그 보다 작은 값보다는 합이 커지기 때문이다.

또한 정렬된 순서에서 가장 큰 값보다 나머지 중 가장 큰 두 값만 확인하면 가장 큰 값에 대해서는 확인이 필요없게 된다. 제외한 나머지 중 가장 큰 두 값을 더해서 가장 큰 값보다 크지 않으면 그 보다 작은 수들은 비교할 필요가 없기 때문이다.