[Swift] Codility Lesson 3 - PermMissingElem

문제

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:

public func solution(_ A : inout [Int]) -> Int

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)].

 

링크

PermMissingElem coding task - Learn to Code - Codility

 

문제 분석

• 정수 N개로 구성된 배열 A가 입력으로 주어진다.
• 배열 A는 1부터 N+1까지의 범위의 정수들로 구성된다.
• 1부터 N+1까지의 범위의 정수들 중 배열에 없는 요소를 찾아 반환한다.

ex) A = [1, 6, 3, 5, 2]

N = 5
1부터 6까지 범위의 정수들 중 4가 배열에 없다.

 

해결방안

1. 배열 A를 Set(집합)으로 변환
2. 1부터 N+1까지의 정수들로 구성된 Set을 생성
3. 둘의 차집합을 계산 (substracting)

 

Solution

public func solution(_ A : inout [Int]) -> Int {
    let setA = Set(A)
    let setB = Set(1...(A.count+1))
    
    return setB.subtracting(setA).first!
}

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