[Codility] Lesson4 (Counting Elements) - PermCheck

2018-09-26

문제

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

문제 이해

주어진 배열 A가 순열인지 아닌지 확인하는 함수를 계산하는 문제입니다. 여기서 순열이란 N개의 정수로 구성된 배열 A에서 1에서 N까지 단 한번만 배열 A에 존재하는 경우 A를 순열이라 부릅니다.

해결 전략

어떤 배열이 순열임을 만족시키는 조건 2개를 문제로부터 유추 할 수 있습니다. 하나는 1에서 N까지 모든 수가 존재해야 하고, 다른 하나는 각 원소가 단 1번만 존재해야 한다는 것입니다.

첫번째 조건을 만족시키기 위해서 1부터 N까지의 합을 이용합니다. N * (N + 1) / 2를 하면 1부터 N까지 원소의 기대되는 합을 구할 수 있습니다. 배열의 각 원소를 더했을 때, 서로의 합이 일치하면 일단 첫번째 조건은 만족하는 것입니다.

하지만 합만 같아서는 배열 A에 단 한번만 존재한다는 조건을 확인할 수 없습니다. 같은 수가 적절히 존재하면 합은 같이 나올 수 있기 때문입니다. 그래서 이 조건을 확인하기 위해서 Set(HashMap)을 선언해서 배열의 각 원소를 순회하며 이 Set에 원소를 넣습니다. 원소를 넣기 전에 Set에 현재 순회하는 원소가 존재하는지 확인합니다. 존재하는 경우 이전에 원소를 넣은 것이기 때문에 중복값이 발견된 것입니다. 이 시점에서 바로 순열이 아님을 판별할 수 있기 때문에 순열이 아님을 나타내는 0을 반환합니다.

코드 (in Swift)

위 해결 전략을 코드로 구현하면 다음과 같습니다. 쉽죠? 😄

public func solution(_ A : inout [Int]) -> Int {
    var countCheckSet = Set<Int>()
 
    let N = A.count
    let expectedSum = N * (N + 1) / 2
    var sum = 0
 
    for element in A {
        if element > N {
            return 0
        }
 
        // found duplication
        if countCheckSet.contains(element) {
            return 0
        }
        else {
            countCheckSet.insert(element)
        }
 
        sum += element
    }
 
    if expectedSum == sum {
        return 1
    }
 
    return 0
}