[코딜리티] codility lesson 6 sorting - Triangle 100%

문제.

A zero-indexed 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:

int solution(int A[], int N);

that, given a zero-indexed 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.

Assume that:

• 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].

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 2009–2017 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

풀이

12345678910111213141516171819

// you can also use imports, for example:
// import java.util.*;
import java.util.Arrays;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        Arrays.sort(A);
        
        
        for( int i = 0 ; i < A.length-2 ; i++){
            if(A[i] < 0 ) continue;
            if((long)A[i] + A[i+1] > A[i+2]) return 1;
        }
        return 0;
    }
}

설명

삼각형을 만들 수 있는 숫자 3개가 배열속에 존재 하는지 찾아보고 . 있으면 1 없으면 0 을 출력 하라.

일단 소트를 해야 하는데, 귀찬아서 라이브러리를 살짝 바르고. 가랏! 매직소트!.

정렬이 된다음에야 간단한다.
-값은 건너 뛴다.
작은 두 변의 합이 가장 큰 변보다 크면 된다. 끝.