An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, 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] = 12

 There are four triangular triplets that can be constructed from elements of this array, namely (0, 2, 4), (0, 2, 5), (0, 4, 5), and (2, 4, 5).


 Write a function:


 public func solution(_ A : inout [Int]) -> Int


 that, given an array A consisting of N integers, returns the number of triangular triplets in this array.


 For example, given array A such that:


   A[0] = 10    A[1] = 2    A[2] = 5

   A[3] = 1     A[4] = 8    A[5] = 12

 the function should return 4, as explained above.


 Write an efficient algorithm for the following assumptions:


 N is an integer within the range [0..1,000];

 each element of array A is an integer within the range [1..1,000,000,000].


영어라 해석하기 귀찮다면 간단하게 문제 설명해주자면

배열에 들어있는 숫자의 의미는 한 변의 길이를 뜻하고 목표는 이 선을 이용해 삼각형을 몇 개 만들 수 있느냐를 구하는것임


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

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

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

조건은 이것만 맞춰주면 얼추 될것같음



아무튼 이해가 안가는건 어떻게 시간복잡도가 O(N^3) 미만이 나올 수 있느냐는것임 ㅡㅡㅋ

빡대가리라.. 열라쉬운 문제인데 그게 궁금해


일단 내가 푼거 공개함.. 스위프트로 작성했음.


public func solution(_ A : inout [Int]) -> Int {//O(N**3)

var cnt:Int = 0

let sortedA = A.sorted()

if A.count > 2 {

for i in 0..<sortedA.count-2 {

for j in i+1..<sortedA.count-1 {

for k in j+1..<sortedA.count {

if isTriangle(P: sortedA[i], Q: sortedA[j], R: sortedA[k], N: A.count) {

cnt += 1

}

}

}

}

}

return cnt

}


func isTriangle(P:Int,Q:Int,R:Int,N:Int) -> Bool {

var isTriangle:Bool = false

if P + Q > R && Q + R > P && R + P > Q {

isTriangle = true

}

return isTriangle

}


var result = [10,2,5,1,8,12]

print("result:(solution(&result))")