Codility: MissingInteger (Python)

주제

Lesson 4: Counting Elements

 

난이도

Medium

 

문제

This is a demo task.
Write a function:
def solution(A)
that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].

 

주어진 리스트에 없는 가장 작은 양의 정수를 찾는 문제이다.

조건은 배열 A의 원소 개수인 N은 1~ 100,000 이며, 각각의 A의 원소는 -1,000,000~1,000,000이 가능하다.

 

 

풀이

가장 작은 양의 정수를 찾아야 하므로, 주어진 list A에서 양의 정수만 따로 빼서 set로 저장한다. (중복값을 제거하기 위해서 set 데이터 구조를 선택함.)

그 후, 가장 작은 값부터 확인하기 위해서 set을 list로 변경 후 sort한다.

리스트에 없는 숫자(missing int)를 1로 가정한다. (양의 정수 중 가장 작은 수이므로.)

sort된 list의 가장 작은 원소부터 반복하며, missing int가 list의 원소보다 작은 순간을 찾는다. 여기서 만약 missing int가 list의 원소와 같다면 missing int의 값을 1씩 늘린다. 

 

Ex. [1,2,3,5]

i = 1, missing_int = 1 이므로, missing_int = 2로 업데이트 한다.

i = 2, missing_int = 2 이므로, missing_int = 3으로 업데이트한다.

i = 3, missing_int = 3 이므로, missing_int = 4로 업데이트한다.

i = 5, missing_int = 4 이므로, 반복문을 break하고 해당 값을 리턴한다. 

 

 

코드

def solution(A):
    positive_set = set()
    for i in A:
        if i > 0:
            positive_set.add(i)

    positive_A = list(positive_set)
    positive_A.sort()

    missing_int = 1
    for i in positive_A:
        if missing_int < i:
            break
        else:
            missing_int += 1

    return missing_int

 

 

시간복잡도

첫번째 반복문 : O(N)

두번째 반복문 : O(N)

따라서 코드 전체의 복잡도는 O(N)이 된다.

 

 

결과

Codility 결과