Triangle

🔗 문제 링크

https://app.codility.com/programmers/lessons/6-sorting/triangle/start/

❔ 문제 설명

An array A consisting of N integers is given. A 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] = 20

Triplet (0, 2, 4) is triangular.

Write a function:

def solution(A)

that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:

A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20

the function should return 1, as explained above. Given array A such that:

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

the function should return 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].

---

💡 풀이 (언어 : Python)

이걸 어떻게 풀지? 전체 탐색 밖에 생각이 안나는데? 하다가 lesson 이름이 sort인 만큼
정렬을 통한 풀이를 생각해보았다. 정렬을 하면 인덱스가 보존이 안되는게 문제인데 반복문을 한번 돌아서 인덱스까지 함께 묶어 튜플로 새로운 리스트에 넣어주면 된다. 하지만 이 문제는 정답 케이스의 인덱스를 요구하지 않으므로 내가 푼 이 과정은 불필요한 과정이었다.
풀이의 핵심 아이디어는 정렬을 했기 때문에 triangle의 세가지 케이스를 다 볼 필요없이 첫번째, 두번째 수를 더하면 세번째 수보다 큰지만 확인하면 되는 것이다.

def solution(A):
    lis = []
    for i, a in enumerate(A):
        lis.append((i, a))

    lis.sort(key = lambda x : x[1])

    for i in range(len(lis)-2):
        if lis[i][1] + lis[i+1][1] > lis[i+2][1]:
            return 1
        
    return 0