[파이썬] Codility - Lesson 3 Time Complexity: PermMissingElem

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

PermMissingElem coding task - Learn to Code - Codility

문제 간단 해석

연속된 int의 list에서 없는 int를 찾는 방법입니다

(예: [2, 3, 1, 5] => 답은 4)

 

문제 풀이

1. 주어진 list (A)의 길이 +1만큼의 0으로 구성된 list (arr)를 만듭니다.

arr = [0] * (len(A)+1)

2. for loop를 통해 A의 각 요소들을 arr에 1로 넣어줍니다.

예를 들어 A에 2가 있으면 arr의 두번째값, 즉 arr[1]을 1로 설정해줍니다.

for a in A:
    arr[a-1] = 1

3. 이후 arr에서 0인 index 값을 찾아 +1를 해준 후 반환합니다.

arr.index(0)+1

전체 코드는 다음과 같습니다.

def solution(A):
    arr = [0] * (len(A)+1)
    for a in A:
        arr[a-1] = 1
    return arr.index(0)+1