Codility_Triangle

6-3. Triangle
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:

class Solution { public int solution(int[] 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].

배열 A가 N개의 정수로 구성되어 있습니다. 삼중항 (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)는 삼각형입니다.

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] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        // 3이하인 경우 삼각형 존재 불가
        if (A.length < 3) {
            return 0;
        }

        // 배열을 오름차순으로 정렬
        Arrays.sort(A);

        for (int i = 0; i < A.length - 2; i++) {
            long P = A[i];
            long Q = A[i+1];
            long R = A[i+2];
            if (P > 0 && P + Q > R) {
                return 1;
            }
        }
        return 0;
    }
}

특이사항으로 계산시 int 범위를 넘어가는 경우가 있어 long 타입으로 변환해서 문제풀이를 하였습니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/6-sorting/triangle/