Codility - Triangle

Codility Lesson 6의 마지막 문제다.

Triangle 이라는 문젠데, 배열 안에 3개의 수가 아래의 조건을 만족하는 지의 여부를 묻는 문제다.

 

A[i] + A[j] > A[k]

A[j] + A[k] > A[i]

A[i] + A[k] > A[j]

(단, 0< i,j,k < N)

 

최대한 for 문을 안쓰고 싶은데, 어떻게 해야할까..

for 문 3개 쓰니깐, 마지막 3문제는 Timeout Error가 발생했다.ㅜㅜ

 

 

 

시간 복잡도: O(N**3) --> 81%의 정답률

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(A):
    # write your code in Python 3.6
    
    A = sorted(A)
    
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            for k in range(j+1,len(A)):
                if A[i] + A[j] <= A[k]:
                    break
                else:
                    if is_triangular(A[i],A[j],A[k]) == 1:
                        return 1
            
    return 0
    pass


def is_triangular(a,b,c):
    if a+b > c and a+c > b and b+c > a:
        return 1
    else:
        return 0

 

크기에 따라서 오름차순으로 정렬하고,

for문 하나로 문제를 푸니 풀렸다!!

 

ex) 1,2,5,8,10,20 로 정렬을 하면,

 

a < b < c이렇게 정렬이 될때,

 

일단 a + c > b 는 당연한 사실 c가 b 보다 크기 때문에.

그리고 c + b > a도 당연한 사실 c,b가 a보다 크기 때문에,

 

그러므로 a + b > c 인지만 확인하면 됨.

 

 

시간 복잡도: O(N*log(N)) --> 100%의 정답률

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    A = sorted(A)
    
    for i in range(len(A)-2):
        if A[i] + A[i+1] > A[i+2]:
            return 1
    
    return 0
    pass

 

관련 유튜브 강의도 있습니다~~

 

https://www.youtube.com/watch?v=IxLlq9RGFI8

 

저의 강의입니다ㅋㅋㅋ