[codility] Sorting - Triangle

문제

N 개의 정수로 구성된 배열 A가 제공됩니다. 삼중 항 (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].
예를 들어 다음과 같은 배열 A를 고려하십시오.

   A [0] = 10 A [1] = 2 A [2] = 5
   A [3] = 1 A [4] = 8 A [5] = 20
삼중 항 (0, 2, 4)은 삼각형입니다.

함수를 작성하십시오.

클래스 솔루션 {public int solution (int [] A); }

즉, N 정수로 구성된 배열 A가 주어지면이 배열에 삼각 삼중 항이 있으면 1을 반환하고 그렇지 않으면 0을 반환합니다.

예를 들어, 다음과 같은 배열 A를 제공합니다.

   A [0] = 10 A [1] = 2 A [2] = 5
   A [3] = 1 A [4] = 8 A [5] = 20
위에서 설명한대로 함수는 1을 반환해야합니다. 주어진 배열 A는 다음과 같습니다.

   A [0] = 10 A [1] = 50 A [2] = 5
   A [3] = 1
함수는 0을 반환해야합니다.

다음 가정을위한 효율적인 알고리즘을 작성하십시오.

N은 [0..100,000] 범위 내의 정수이며;
배열 A의 각 요소는 [-2,147,483,648..2,147,483,647] 범위의 정수입니다.

사고방식

먼저 삼중항의 여부만 검증하면 되기 때문에 배열을 내림차순으로 비교를 하기위해 배열 정렬을 해줍니다.

예시처럼 배열이  A = [10, 2, 5, 1, 8, 20] 이라면 정렬하게 되면 A = [20, 10, 8, 5, 2, 1] 로 정렬이 됩니다. 정렬이 된 배열을 for 문을 이용하여 비교를 하게 합니다.

세 배열씩 비교를 하다가 만약에 조건에 일치한다면 1 을 반환합니다. 다 비교해서 조건에 일치하지 않는다면 0 을 반환합니다.

해결코드

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let result = 0;
    A.sort((a,b)=> {return b-a})
    for(let i=0; i<A.length-2; i++){
        if(A[i+1]+A[i+2]>A[i]) return 1
    }
    return result
}

app.codility.com/demo/results/trainingX4EYTS-T9H/

Test results - Codility

에필로그

처음에는 삼중항을 모두 비교를 했었는데 첫번째 조건이 맞기만 하면 최대값에서 어떤 값이든 더하면 당연히 크기 때문에 나머지 두 조건은 비교하지 않아도 된다고 생각하여 나머지 조건은 제거했습니다.

if(A[i+1]+A[i+2]>A[i] && A[i]+A[i+2]>A[i+1] && A[i+1]+A[i]>A[i+2])