[Swift] Codility Lesson 4 - PermCheck

문제

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

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

is a permutation, but array A such that:

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

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

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

that, given an array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

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

the function should return 1.

Given array A such that:

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

the function should return 0.

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..1,000,000,000].

 

문제 링크

PermCheck coding task - Learn to Code - Codility

GitHub

GitHub - yoohyebin/swift

 

문제 분석

• N개의 정수로 구성된 배열 A가 순열인지 아닌지 판단하는 문제이다.
• 배열 A가 순열이라면 1, 아니라면 0을 반환한다.
• 이번 문제에서는 1부터 N까지의 정수를 1개씩 모두 갖고 있는지 판단해야 한다.

순열: 서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관있게 선택하는 혹은 나열하는 것

 

해결 방안

1. 1부터 N까지의 정수들을 값으로 갖는 Set(집합) 생성
2. Set과 배열 A의 차집합을 계산
   • 차집합이 있다면 순열이 아니기 때문에 0 반환
   • 차집합이 없다면 순열이 맞기 때문에 1 반환

Solution

public func solution(_ A : inout [Int]) -> Int {
    let setB = Set(1...A.count)
    return setB.subtracting(A).isEmpty ? 1 : 0
}

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