[Codility] 6. Triangle

문제 링크

Triangle

문제 요약

A : N개의 정수로 구성 된 배열
(P, Q, R)이 삼각형일 때

0 ≤ P < Q < R < N --> idx
A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].

배열에 삼각형이 있으면 1, 없으면 0을 리턴

요구사항

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]

-> OverFlow 한방 먹었다...

코드

1. 우선 배열 개수가 3개보다 적은지 체크
2. 합이 될 변수는 Int(=Int32)보다 큰 Int64로 선언
   (OverFlow 발생 요인)
3. 만족하는 인덱스 개수를 반환하는게 아니고, 중복된 인덱스를 확인할 필요도 없으므로 그냥 정렬해도 된다.
4. 만약 Triangle 이 (10, 20, 28)라고 하자.
   여기서 세가지 조건을 적용해보면
   10 + 28 > 20
   20 + 28 > 20
   10 + 20 > 28

맥스값이 들어간 조건은 항상 성립하는 것을 볼 수 있다.
따라서 마지막 세번째 조건 즉, 가장 작은수와 두번째로 작은 수의 합이 맥스값보다 큰지만 확인하면 된다.

O(N*log(N))

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let cnt = A.count
    var addedNum: Int64

    if(3 > cnt) { return 0 }
    A.sort()
    for i in 0..<cnt-2 {
        if(A[i] < 0) { continue }
        addedNum = Int64(A[i]) + Int64(A[i+1])
        if(addedNum > A[i+2]) { return 1 }
    }
    return 0
}