[Codility] Lesson 6 : Triangle - JAVA

문제

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].
 
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A)에 입력되는 배열 A의 길이(N)는 0 ~ 100,000이고
배열 A에 저장되는 정수는 −2,147,483,648 ~ 2,147,483,647까지이다.

배열 A 안에서 정수 3개를 꺼냈을 때 총 몇 개의 삼각형이 만들어지는지 확인하는 문제이다.

삼각형이 만들어지는 조건은
        A[P] + A[Q] > A[R],
        A[Q] + A[R] > A[P],
        A[R] + A[P] > A[Q].
이다. (0 ≤ P < Q < R < N)

예를 들어 배열 A가

        A[0] = 10    A[1] = 2    A[2] = 5
        A[3] = 1      A[4] = 8    A[5] = 20

일 때 A[2] + A[4] > A[0]인 조건에서 삼각형이 만들어지므로 1을 반환하면 된다.
만약 삼각형이 만들이지지 않는 경우 0을 반환하면 된다.

 

풀이 - 1

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

 

 

'풀이 - 1'에 대한 회고

 

처음에 문제를 잘못 이해했다.

삼각형이 몇 개 만들어지는지 계산하는건가 해서 소스코드를 작성했는데

엄청 복잡한 코드가 되버렸다.

그런데 답이 완전 틀리다고 나와서 왜 그런지 다른 사람의 문제 풀이 방식을 봤다.

알고보니 문제는 삼각형을 만들 수 있다면 1을, 만들 수 없다면 0을 반환하는 것!

 

 

기왕 틀린거 다른 사람의 풀이를 참고해서 소스코드를 작성했다.

그랬더니 바로 100점!

 

 

이건 뭐... 문제도 잘못읽고 할 말이 없다...