[Codility] (Lesson6 | Sorting)Triangle - JavaScript

문제

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
}

최종결과

출처

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