/ ALGORITHM

(codility with python) PermMissingElem


lesson3 - PermMissingElem

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

sort한 이유가 A의 값과 A의 인덱스 값(인덱스 + 1)을 비교했을때 서로 같지 않으면 해당 값이 miss된 값이기 때문에 not in A가 아니라 인덱스 +1 != A[i]를 비교해야 한다 이후 for문을 통해 값이 Return되지 않으면 원래 A의 LEN값에 +1을 해준 값을 리턴해야 한다

O(n^)의 시간복잡도

# error 0%

def solution(A):
    A.sort()
    arr = [i for i in range(1, len(A) + 1)]
    
    for i in arr: 
        if i not in A:
            return i
        
solution([2,3,5,1])


다른풀이

O(N) or O(N * log(N))의 시간복잡도

def solution(A):
    A.sort()
    arr = [i for i in range(1, len(A) + 1)]
    
    for i in range(len(arr)): 
        if arr[i] != A[i]:
            return arr[i]
    return len(A) + 1
        
solution([2,3,5,1])


다른풀이

O(N) or O(N * log(N))의 시간복잡도

def solution(A):
    return 1 if not A else sum([i for i in range(1, len(A) + 2)]) - sum(A) 

solution([2, 3, 1, 5])