코딜리티 | lesson3 - Time Complexity : PermMissingElem (python)

💻lesson3 - PermMissingElem

1. 문제

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function:

def solution(A)

that, given an array A, returns the value of the missing element.
For example, given array A such that:

A[0] = 2
A[1] = 3	
A[2] = 1
A[3] = 5

the function should return 4, as it is the missing element.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

2. 문제 접근

배열에 1에서 n까지의 수가 있는데 딱 한 숫자가 빠져있고 그 빠져있는 숫자를 찾는 것이 이 문제의 목적인가보다.
이 문제를 풀기 위해선 반복문은 필수일 듯하고 O(N^2)가 되지 않도록 최대한 O(N)이 되도록 노력하면서 문제를 풀어봐야겠다.
우선은 리스트보다는 집합을 사용하면 시간복잡도가 더 작기 때문에 집합을 사용한다. 그 다음에 반복문으로 집합에 해당 숫자가 있는지 포함여부를 확인하기로 한다.

<시간 복잡도 참고>
1. 리스트

2. 집합
   

3. 풀이 - python

def solution(A):
    A = set(A)
    for i in range(1, len(A)+2):
        if(i in A):
            continue
        else:
            return i

4. 결과

5. 마무리

이번 문제를 풀면서 리스트가 아닌 집합을 사용하여 시간복잡도를 줄이자라는 전략이 제대로 먹히면서 성공적으로 문제를 풀 수 있었다!
한번에 끝나니깐 기분이 좋구만요
다음 문제도 계속 이렇게 풀어보자! 화이팅요