[Python] 6.4. Triangle

https://app.codility.com/demo/results/trainingX6JCFR-MQJ/

Test results - Codility

인풋 데이터의 사이즈가 10만 아래이기 때문에 완전탐색하기로 결정하였다.

순열을 생성해서 모든 경우의 수에 대해서 삼각형 결정조건을 조사하였다.

---

Task Score

100%

Correctness

100%

Performance

100%

Detected time complexity

O(N * log(N))

def next_perm(a):
    i = len(a)-1

    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    
    if i <= 0:
        return False
    
    j = len(a)-1

    while a[i-1] >= a[j]:
        j -= 1
    
    a[i-1], a[j] = a[j], a[i-1]

    j = len(a)-1

    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

    return True


def solution(A):
    
    if len(A) < 3:
        return 0

    N = len(A)
    _A = sorted(A)
    p = [0]*(N-3) + [1]*3

    while True:
        num = [p[i]*_A[i] for i in range(N) if p[i]*_A[i] > 0]

        if len(num) < 3:
            return 0

        if num[0]+num[1] > num[2] and num[0]+num[2] > num[1] and num[1]+num[2] > num[0]:
            return 1

        if not next_perm(p):
            break

    return 0