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].
첫 풀이
maxInt를 포함한 테스트 하나에서 실패, 퍼포먼스에서 O(N)³이 나오면서 실패하였다.
일단 생각없이 요구사항 충실, 왠지 그냥 정렬해야 할꺼 같으니까 정렬하였다.
import java.util.Arrays;
class Solution {
public int solution(int[] A) {
Arrays.sort(A);
int result = 0;
for(int i=0; i<A.length-2; i++) {
int P = A[i];
for(int j=i+1; j<A.length-1; j++) {
int Q = A[j];
for(int k=j+1; k<A.length; k++) {
int R = A[k];
result = isTriplet(P, Q, R);
if(result == 1) {
break;
}
}
if(result == 1) {
break;
}
}
if(result == 1) {
break;
}
}
return result;
}
private int isTriplet(int P, int Q, int R) {
int isTriplet = 1;
if(!((P + Q) > R)) {
isTriplet = 0;
}
if (!((Q + R) > P)) {
isTriplet = 0;
}
if (!((R + P) > Q)) {
isTriplet = 0;
}
return isTriplet;
}
}두번째 풀이
숫자를 가져오는 부분에서 정렬한 후 비교하면 오름차순이므로 뒤와 비교할 필요는 없으므로 (뒤로 갈수록 숫자가 커지므로 어차피 결과는 false)
O(N)으로 풀 수 있겠다는 생각이 들었다.
결과는 O(N*log(N)) 이 나오면서 성공.. 인줄 알았으나 테스트 하나에서 실패하였다.
첫번쨰 풀이와 같은 곳에서 결과 도출에 실패하였다.
overflow test, 3 MAXINTs 에서 maxInt가 2개있어 실패하였다.
import java.util.Arrays;
class Solution {
public int solution(int[] A) {
Arrays.sort(A);
int result = 0;
for(int i=2; i<A.length; i++) {
int P = A[i-2];
int Q = A[i-1];
int R = A[i];
result = isTriplet(P, Q, R);
if (result == 1) {
break;
}
}
return result;
}
private int isTriplet(int P, int Q, int R) {
int isTriplet = 1;
if(!((P + Q) > R)) {
isTriplet = 0;
}
if (!((Q + R) > P)) {
isTriplet = 0;
}
if (!((R + P) > Q)) {
isTriplet = 0;
}
return isTriplet;
}
}그래서 maxInteger 일때 조건을 넣어줬는데
import java.util.Arrays;
class Solution {
public int solution(int[] A) {
Arrays.sort(A);
int result = 0;
for(int i=2; i<A.length; i++) {
int P = A[i-2];
int Q = A[i-1];
int R = A[i];
result = isTriplet(P, Q, R);
if (result == 1) {
break;
}
}
return result;
}
private int isTriplet(int P, int Q, int R) {
int isTriplet = 1;
if(!((P + Q) > R)) {
isTriplet = 0;
}
if (!((Q + R) > P)) {
isTriplet = 0;
}
if (!((R + P) > Q)) {
isTriplet = 0;
}
if(Q == R && Q == Integer.MAX_VALUE) {
isTriplet = 1;
}
return isTriplet;
}
}
이번에는 0, maxInteger, maxInteger case에서 실패하였다.
마지막 풀이
모든 케이스 제거로 성공하였다.
근데 이러면 하드코딩을 한 거 같아 찝찝하다. 어떻게 풀어야 할까?
import java.util.Arrays;
class Solution {
public int solution(int[] A) {
Arrays.sort(A);
int result = 0;
for(int i=2; i<A.length; i++) {
int P = A[i-2];
int Q = A[i-1];
int R = A[i];
result = isTriplet(P, Q, R);
if (result == 1) {
break;
}
}
return result;
}
private int isTriplet(int P, int Q, int R) {
int isTriplet = 1;
if(!((P + Q) > R)) {
isTriplet = 0;
}
if (!((Q + R) > P)) {
isTriplet = 0;
}
if (!((R + P) > Q)) {
isTriplet = 0;
}
if(P > 0 && Q == R && Q == Integer.MAX_VALUE) {
isTriplet = 1;
}
return isTriplet;
}
}베스트 답안
여기를 참조 하였다.
- 크기가 3이하 일 경우 처리 필요
- 요소의 범위가 정수 최소 ~ 최대 이므로 더했을 경우 long 형으로 처리해야 함
- 정렬을 우선 한다.
- 정렬 된 상태 이면 아래는 무조건 만족하므로 A[P] + A[Q] > A[R] 에 대해서만 체크함.
내 고민을 기본자료형을 long으로 바꾸면서 해결한 예제이다.
또 정렬함으로써 조건 중 몇개가 소거되었다.
A[R] + A[P] > A[Q] (첫번째, 마지막 합은 중간보다 항상 큼)
A[Q] + A[R] > A[P] (중간, 마지막 합은 첫번째보다 항상 큼)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;
}