[Demo] MissingInteger

[문제]

Codility f&q에서 제공되는 데모 문제

Codility

 

[코드]

시간복잡도 : O(N)

* Python list의 in 연산자의 시간복잡도는 O(N)임

def solution(A):
    # write your code in Python 3.6
    answer = 1
    check = [0 for i in range(1000002)]
    A.sort()
    for num in A :
        if num > 0 :
            if answer == num :
                check[num] = 1
                answer = answer + 1
            elif check[num] != 1 :
                break
    return answer

 

* 참고) Python 연산자 별 시간 복잡도

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그