코딜리티 Time Complexity - PermMissingElem (파이썬)

Time Complexity - PermMissingElem

 

* 프로그래밍 주안점

1. 가독성

2. 성능

 

문제링크: https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

 

설명 (요약)

1..(N+1) 에서 순서대로 되어 있지 않은 값 찾기 예: A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5 결과: 4

 

고려사항

• 비어있는 리스트는 1 반납
• N 까지 있는 리스트는 N+1 반납

 

코드

 

def solution(A):
    if not A:
        return 1

    A.sort()
    for i in range(len(A)):
        if (i + 1) != A[i]:
            return i+1
    
    return len(A)+1


solution([2,3,1,5])     # return 4

 

 

Github: https://github.com/oksk1111/algorithm_python/blob/main/codility_TimeComplexity_PermMissingElem.ipynb

GitHub - oksk1111/algorithm_python

 

 

결과

 

 

Analysis

Detected time complexity: O(N) or O(N*log(N))