'Algorithm'에 해당되는 글 23건

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.

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

Sort 을 하게되면 0 < a ≤ b ≤ c ,  (a + c ≥ b) & (b + c ≥ a) 이다.

A[Q] + A[R] > A[P], A[R] + A[P] > A[Q] 조건을 자동으로 만족한다.  

물론 여기서의 범위는 음수도 들어가기 때문에 좀 문제가 이상해지긴 하지만 세변의 길이가 양수여야하는 삼각형의 조건에서는 충분히 만족한다.

또한 A[i], A[i+1], A[i+2] 만을 고려한 이유는 어차피 A[i+2] 이후의 값은 A[i+2]보다 크거나 같기 때문에 고려할 필요가 없기 때문이다.

import java.util.*;

class Solution {
    public int solution(int[] A) {
        
        long P;
        long Q;
        long R;
        
        if(A.length < 3){
            return 0;
        }
        
        Arrays.sort(A);
        
        for(int i = 0; i < A.length - 2; i++){
            P = A[i];
            Q = A[i+1];
            R =  A[i+2];
            if(P + Q > R){
                return 1;
            }
        }
        
        return 0;
    }
}