[Codility] Sorting - Triangle 풀이
예문
https://app.codility.com/programmers/lessons/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 : N개의 정수로 구성 된 배열
- (P, Q, R)이 삼각형일 때
0 ≤ P < Q < R < N
A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
- 배열에 삼각형이 있으면 1, 없으면 0을 리턴하라!
풀이
- 배열 크기가 3이하 일 경우 처리 필요
- 각 요소의 범위가 정수 최소 ~ 최대 이므로 더했을 경우 long 형으로 처리해야 함
- 정렬을 우선 한다.
- 정렬 된 상태 이면 아래는 무조건 만족하므로 A[P] + A[Q] > A[R] 에 대해서만 체크함.
A[R] + A[P] > A[Q] (첫번째, 마지막 합은 중간보다 항상 큼)
A[Q] + A[R] > A[P] (중간, 마지막 합은 첫번째보다 항상 큼)
제약사항
- N의 범위는 정수 [0..100,000]
- 배열A의 각 요소의 범위는 정수 [−2,147,483,648..2,147,483,647]
코드
import java.util.Arrays;
public int solution(int[] A) {
int N = A.length;
if (3 > N) return 0;
Arrays.sort(A);
for (int i = 0; i < N - 2; i++) {
long P = A[i], Q = A[i + 1], R = A[i + 2];
if (P + Q > R) return 1;
}
return 0;
}