[Codility] Prefix Sums - MinAvgTwoSlice 풀이
예문
https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/
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 형으로 처리해야 함
- 정렬을 우선 한다.
- 위에 나온 식으로 더해서 모두 true 일 경우 루프 중단.
제약사항
- N의 범위는 정수 [0..100,000]
- 배열A의 각 요소의 범위는 정수 [−2,147,483,648..2,147,483,647]
코드
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++){
int passSum = 0;
long P = A[i], Q = A[i+1], R = A[i+2];
if(P + Q > R) passSum++;
if(Q + R > P) passSum++;
if(R + P > Q) passSum++;
if(3 == passSum) return 1;
}
return 0;
}