Lesson 6 - Triplet

GwanMtCat·2023년 5월 29일
0
post-custom-banner

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;
}
post-custom-banner

0개의 댓글