[Codility - Counting Elements] Triangle

문제 링크

Triangle coding task - Learn to Code - Codility

- N은 100,000 이하의 수이다. 따라서, O(NlogN)이하의 알고리즘을 구현해야 한다.

 

function solution(A) {
    const positiveArray = A.filter((elem)=>elem > 0).sort((a,b)=>a-b)
    for(let i = 0; i < positiveArray.length-2; i++){
        if(positiveArray[i]+positiveArray[i+1] > positiveArray[i+2]) return 1
    }
    return 0
}

 

- 음수는 어차피 후보가 될 수 없으니 제거하고, 양수만 남기기 위해 filter 메서드 사용하고, 오름차순 정렬한다.

 

- 이 후, 연속적인 3개의 element를 비교하면 된다. 왜냐하면, 이 외의 조합들은 작은 두 수를 더할 때 최상의 시나리오가 나오지 않기 때문이다.