(코딜리티) Lesson 6. [sorting] : triangle- python

이전 문제부터는 여태 수학적으로 정의 되어있거나, 수 많은 테스트 케이스를 생각해서 증명해내기에 머리에 한계가 있어서 그런지.. 이것 저것 추측하면서 해보고 이렇게 하면 되는 구나하고 이해하는 단계가 된 것 같습니다.. 공부하는데 영 찝찝하네요..

 

문제 : app.codility.com/programmers/lessons/6-sorting/triangle/

Triangle coding task - Learn to Code - Codility

문제 내용

N개의 배열 A를 주어질 때, 만약 0 <= P < Q < R < N일 때, 

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

를 만족하면 1을 return하고, 그 외는 0을 return하여라.

 

예를 들어,

A = [10, 2, 5, 1, 8, 20]일 때는 (0, 2, 4)가 조건을 만족하므로 return 1

A = [10, 50, 5, 1]일 경우는 return 0

제한 사항

• N는 0~100,000
• 배열 A의 각 요소는 -2,147,483,648~2,147,483,648

코드

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

    A = sorted(A)
    
    for i in range(len(A)-1, 1, -1):
        if A[i] < A[i-1] + A[i-2]:
            return 1

    return 0

해설

배열을 정렬 한 후, 큰 수 부터 인접한 숫자들만 비교하여 A[P] + A[Q] > A[R]만 만족한다면, 다른 조건을 만족하기에 이 부분만 비교하면 됩니다.