[codility] Triangle

Triangle

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

Task Score

93%

Correctness

90%

Performance

100%

---

 

주어진 배열 A에서

• A[P] + A[Q] > A[R],
• A[Q] + A[R] > A[P],
• A[R] + A[P] > A[Q].

를 만족하는 세 숫자가 존재하면 1을 반환하고, 아니면 0을 반환하는 문제이다.

일단 시간복잡도가 O(NlogN)이기 때문에 for문 3개를 돌리는 것은 안될 말이고.. 그렇다고 for문을 3개로 나눠서 뭐 어떻게 저떻게 하자니 그건 또 아닌 것 같고..

그래서 sort로 A를 정렬해주고 연속된 세 숫자를 비교해주는 방식을 사용했다. 크기 순서대로 정렬해서 처음에는 세가지 조건을 모두 &&(and)로 묶어서 if의 조건문으로 넣어주었는데, 조건문의 갯수와 상관없이 계속 93%가 나온다....ㅠㅠ 테스트 케이스 중 한가지를 계속 만족시키지 못하는데, 그것도 만족할 수 있도록 다른 방법도 더 생각해봐야겠다.

 

x
// you can also use imports, for example:
import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int solution(int[] A) {
        
        Arrays.sort(A);
        
        for (int i = 0; i < A.length - 2; i++) {
            
            if (A[i] + A[i + 1] > A[i + 2]) 
                return 1;
        }
        
        return 0;
    }
}