문제 // Codility // Sorting // Triangle

업데이트 :: 2018.08.21

---

• 문제
• 코드
• 결과

문제

Determine whether a triangle can be built from a given set of edges.

코드

1차 풀이

class Solution {
    public int solution(int[] A) {

        // 삼각형을 만족하는 3개의 인자
        // (P, Q, R) 0 ≤ P < Q < R < N

        // [10, 2, 5, 1, 8, 20] => (10, 5, 8)
        // [규칙] 최대항이 나머지 2개의 항보다 작으면 삼각형

        if(A.length < 3) return 0;

        int lineA = 0;
        int lineB = 0;
        int lineC = 0;
        for(int i=0; i<A.length-2; i++) {
            lineA = A[i];
            for(int j=i+1; j<A.length-1; j++) {
                lineB = A[j];
                for(int k =j+1; k<A.length; k++) {
                    lineC = A[k];
                    int sum = lineA + lineB + lineC;
                    int max = Math.max(Math.max(lineA, lineB), lineC);
                    if(max < sum - max) {
                        return 1;
                    };
                }
            }
        }
        return 0;
    }
}

2차 풀이

import java.util.*;
class Solution {
    public int solution(int[] A) {

        if(A.length < 3) return 0;
        Arrays.sort(A);

        int max, lineA, lineB;
        for(int i=2; i<A.length; i++) {
            max = A[i];
            for(int j=0; j<i-1; j++) {
                lineA = A[j];
                for(int k=1; k<i; k++) {
                    lineB = A[k];
                    if(max < lineA + lineB) {
                        return 1;
                    };
                }
            }
        }
        return 0;
    }
}

3차 풀이

import java.util.*;
class Solution {
    public int solution(int[] A) {

        if(A.length < 3) return 0;
        Arrays.sort(A);

        int max, lineA, lineB;
        for(int i=0; i<A.length-2; i++) {
            for(int j=i+1; j<A.length-1; j++) {
                if((long) A[j+1] < (long) A[i] + (long) A[j]) {
                    return 1;
                };
            }
        }
        return 0;
    }
}

4차 풀이

import java.util.*;
class Solution {
    public int solution(int[] A) {

        if(A.length < 3) return 0;
        Arrays.sort(A);

        // == 뒤에서부터 돌면 비교 갯수가 감소 ==
        for(int i=A.length-1; i>=2; i--) {
            if((long) A[i] < (long) A[i-1] + (long) A[i-2]) {
                return 1;
            }
        }
        return 0;
    }
}

결과

1차 68%

• 정확 : 90%
• 성능 : 33%

2차 75%

• 정확 : 90%
  • extreme_arith_overflow1 (overflow test, 3 MAXINTs)
• 성능 : 50%
  • large_negative(chaotic sequence of negative values from [-1M..-1], length=100K)
  • large_negative2(chaotic sequence of negative values from [-10..-1], length=100K)
  • large_negative3(sequence of -1 value, length=100K)

3차 81%

• 정확 : 100%
• 성능 : 50%
  • large_negative(chaotic sequence of negative values from [-1M..-1], length=100K)
  • large_negative2(chaotic sequence of negative values from [-10..-1], length=100K)
  • large_negative3(sequence of -1 value, length=100K)

4차 100%

• 정확 : 100%
• 성능 : 100%

---

Created by MoonsCoding

e-mail :: jm921106@gmail.com