Time complexity - codility

 

def solution(A):

    N =len(A)

    result = (N+1)*(N+2)/2

    x = result-sum(A)

    return x

 

 

A의 배열은 1부터 N+1까지 정수를 포함하는 배열이다.

그 중에서 임의의 정수 딱 하나가 빠져있다.

함수 기능을 이용해서 빠진 정수를 구하는 문제.

 

1+2+....+N+1까지의 정수 합에서 A배열의 합을 빼주면

그 중에 빠진 정수 x를 구할수 있다.

 

이 답안은 점수 100%였다.

 

 

def solution(A):

    N =len(A)

    for x in range(1,N+2):

        if x not in A:

            return x

 

이 답안은 정확도 테스트는 모두 통과했지만

시간 복잡도 테스트를 통과하지 못했다.

복잡도가 N^2라서 실행시간이 기준을 초과했다.

 

맨날 사용하던 for과 if not in 함수가 범위가 커졌을때는

좋지 않다는거, 오히려 덧셈을 활용하는게 시간을 단축시킬수 있다.