Codility Lesson 06 - Triangle( JAVA )

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

Triangle coding task - Learn to Code - Codility

 

문제

- N개의 정수들로 이루어진 A배열이 주어진다.

- (P, Q, R)은 triangular다.

• 0 ≤ P < Q < R < N

• A[P] + A[Q] > A[R],
• A[Q] + A[R] > A[P],
• A[R] + A[P] > A[Q]

- 예시 : A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

- Tripler(0,2,4) is triangular

- return 1;( or return 0; )

 

제한조건

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

N은 0 ~ 100,000 사이의 정수이다.

A의 각각의 원소들은 −2,147,483,648 ~ 2,147,483,647 사이의 정수이다.

 

풀이

- N이 0, 1, 2일 경우 예외처리를 해준다.

- 2번째 제한 조건을 보면 int의 범위를 넘어가는 경우가 생기는 것이 예상되므로, 변수들을 float로 계산한다.

- A배열을 오름차순 정렬 후, 3개씩 그룹으로 형성하여 순차적으로 triangular 조건에 부합하는지 확인한다.

  이 때, 각 원소가 < 0 이하인 경우는 건너 뛴다.

- triplet이라는 메소드를 만들어서 boolean을 반환해준다( 조건에 부합하면 true, 조건에 부합하지 않으면 false )

 

예상 시간복잡도 : O(N) - For문을 모두 순회하기 때문

 

소스코드

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

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {

    boolean triplet( float a, float b, float c ){
        boolean check = false;
        
        if( a+b > c && a+c>b && b+c>a ){
            check = true;
        }

        return check;
    };

    public int solution(int[] A) {
        // write your code in Java SE 8
        if( A.length < 3 ){
            return 0;
        }

        int answer = 0;
        Arrays.sort(A);
        for( int i=2; i<A.length; i++ ){
            if( A[i-2] < 0 ) continue;
            if( triplet( (float)A[i-2], (float)A[i-1], (float)A[i] ) ){
                answer = 1;
                break;
            }
        }

        return answer;
    }
}