Triangle

https://app.codility.com/programmers/lessons/6-sorting/triangle/

Triangle coding task - Learn to Code - Codility

 

주어진 정수 배열에서 조건을 만족하는 세 개의 정수가 있는지 체크해야한다.

 

완전 탐색으로 풀면 시간 복잡도를 만족하지 못할 듯하다.

 

배열을 정렬하고,

 

연속된 3개의 원소를 꺼내어 조건이 맞는지 체크하고,

 

조건을 만족하지 못하면 index를 1 증가시켜 다시 연속된 3개의 원소를 꺼내어 조건이 맞는지 체크한다.

 

그런데 배열의 원소 범위가 int 의 min_value ~ max_value 이므로.. 조건을 체크할 땐 long으로 형변환이 필요하다.

import java.util.*;

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);

        for (int i = 0; i < A.length - 2; i++) {
            if (isTriangle(A[i], A[i+1], A[i+2])) return 1;
        }

        return 0;
    }

    boolean isTriangle(long a, long b, long c) {
        return a + b > c && b + c > a && c + a > b;
    }
}