Codility - Triangle (Sorting) [Python]

 

 

 문제

 

app.codility.com/programmers/lessons/6-sorting/triangle/

Triangle coding task - Learn to Code - Codility

 

 

 

 

 

 

 문제 상황

 

- 주어진 배열을 삼각형 한 변 길이의 집합이라고 할 때 세 변으로 한개의 삼각형을 만들 수 있는 경우가 존재하면 1을 반환, 없으면 0을 반환한다.

 

 

 

 

 

 

 해결 전략

 

 

 

 

 

 

 

 코드

 

def solution(A):
    if len(A) < 3 : return 0
    A.sort()
    for i in range(len(A)-2):
        if A[i]+A[i+1] > A[i+2] : return 1
    return 0
 

 

 

 

 

 

 

 

 

 해설

 

- 헷갈렸던 부분은 전수 조사를 해야하는가의 문제이다. 예를 들어, 1 2 4 7 8 의 경우에서, 1 2 4 나 2 4 7의 경우 삼각형이 되지 않는다. 하지만 2 7 8 의 경우 삼각형이 되어서 그런 부분을 검색하려면 다시 O(N^2)~O(N^3)이 되는 것이었다. 하지만 결국 4 7 8 에서 되는 경우가 생기므로 저렇게 풀이해도 가능하다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 확실히 Codility는 수학적 문제가 많다. 수학적으로 개념을 엄밀히 증명할 필요가 있다. 개념 하나로 O(N^3)에서 O(NlogN)이 되었다.

 

- Python에서는 문제가 없었지만 Java의 경우 2,147,483,645 + 2,147,483,646 > 2,147,483,647의 범위에서 오버플로우가 발생하였다. 변수가 가질 수 있는 최대 값이 조건이므로 그 합은 당연히 오버플로우가 발생할 수 밖에 없다. 이를 해결하는 방법은 항을 이항해 A[i]>A[i+2]-A[i+1]을 하면 된다.