문제
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
- 먼저 A 배열을 sort를 이용해 내림차순으로 정렬 (오름차순으로 정렬해도 무관)
sort를 이용해 A 배열의 가장 큰 값을 찾을 수 있고 그 다음 큰 두 수의 합이 가장 큰 값보다 큰지 비교를 통해 빠르게 답을 찾아갈 수 있다. - A 배열의 첫번째 값에서 두번째와 세번째 뺐을때 0보다 작다면 삼각형이 될 수 있는 세 수를 찾았다.
- 두번째 수에서 첫번째와 세번째를 빼고, 세번째 수에서 첫번째와 두번째 수를 뺐을 때 둘 다 0 보다 작으면 삼각형이 되는 세 수가 된다.
- 삼각형이 되는 세 수를 찾으면 바로 1을 리턴해준다.
- 예외 사항으로 첫번째 수가 음수라면 continue로 넘어간다. (삼각형의 변의 길이가 음수가 될 수 없기 때문이다.)
코드
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
}최종결과
출처
