Lesson 6(Sorting) - 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가 주어지면 A의 각기 다른 3인덱스의 값이 다른 두 값의 합보다 작으면 삼각형으로 판단하여 1을 반환하고 없을 경우 0을 반환하는 문제이다.

 

 풀이

1차 제출

// you can also use imports, for example:
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) {
        Arrays.sort(A);

        for(int i=1; i<A.length-1; i++){
            if( A[i-1] + A[i] > A[i+1] && A[i] + A[i+1] > A[i-1] && A[i+1] + A[i-1] > A[i]){
                return 1;
            }
        }

        return 0;
    }
}

* 주의 사항
[2147483647, 2147483646, 2147483645] 인 배열로 테스트 했을 경우
삼각형을 구성할수 있어 값을 1을 반환하여야 하지만, P+Q > R 으로 비교하면 오버플로우가 발생하여 값이 틀립니다.
1문제 틀려 93점을 받았네요.

A[i-1] + A[i] > A[i+1] ->  A[i-1] > A[i+1] - A[i] 로 변경하여 오버플로우를 피해봅시다.

// you can also use imports, for example:
import java.util.Arrays;

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

        for(int i=1; i<A.length-1; i++){
            if( A[i-1] > A[i+1] - A[i] && A[i]> A[i-1] - A[i+1]  && A[i+1] > A[i] - A[i-1] ){
                return 1;
            }
        }

        return 0;
    }
}

삼각형을 이룰려면 크기가 비슷한 길이와 비교하도록 오름차순 정렬을 하여 해당 인덱스의 앞과 뒤의 값과 비교하여 삼각형을 구성할 수 있는지 확인합니다.

 결과

주소 : app.codility.com/demo/results/training6WJJBM-GPG/

제출결과1

제출결과2

어렵진 않았지만, 오버플로우 때문에 2번 시도 했네요.
정렬이 들어가 있어 시간 복잡도는 N*log(N)이 나왔네요.