An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
For example, consider array A such that:
A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
Triplet (0, 2, 4) is triangular.
Write a function:
function solution(A);
that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.
For example, given array A such that:
A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
the function should return 1, as explained above. Given array A such that:
A[0] = 10 A[1] = 50 A[2] = 5
A[3] = 1
the function should return 0.
Write an efficient algorithm for the following assumptions:
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].
이 문제는 배열 중 삼각형을 만들 수 있는 3개의 정수가 있다면 1을 리턴하고 없다면 0을 리턴하는 간단한 문제이다.
효율성과 음수를 고려해 문제를 풀어야 한다.
그리고 Sorting으로 분류돼있기 때문에 정렬을 통해 어떻게 해결할 수 있을지 고민하는 것이 필요하다.
삼각형의 세 변의 길이는 두 변의 길이의 합이 나머지 한 변의 길이보다 커야하는 이론을 알고 있어야한다.
A+B > C
B+C > A
A+C > B
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
let answer = 0;
A.sort((a,b)=>b-a);
for(let i = 0; i<A.length; i++){
let tmp = A[i];
if(tmp < 0) continue
for(let j = i+1; j<A.length; j++){
if(tmp - (A[j] +A[j+1]) < 0){
let n = A[j] - (tmp + A[j+1]);
let m = A[j+1] - (tmp + A[j]);
if(n<0&&m<0) return answer = 1
}
}
}
return answer
}