Codility demo test 코딜리티 데모테스트

코딜리티의 데모 테스트의 문제는 이렇습니다.

 

저는 언어를 Swift4로 선택했습니다.

하하.

 

먼저 문제 해석 :)

 

N개의 정수 중 A배열이 주어지면 A에서 발생하지 않은 가장 작은 양의 정수를 리턴하세요.

예를 들어 A= [1,3,6,4,1,2]이면 함수는 5를 리턴해야 합니다.

A = [1,2,3]이면 함수는 4를 리턴해야 합니다.

A = [-1,-3]이면 함수는 1을 리턴해야 합니다.

 

블라블라 효율적인 알고리즘을 작성해주라.

 

N은 [1.. 100,000] 범위의 정수이며 A의 각 요소는 [-1,000,000.. 1,000,000]입니다.

 

---

 

일단 데모 테스트를 풀어보자.

 

핵심은 주어진 A배열에서 발생하지 않은 가장 작은 양의 정수를 리턴해야 합니다.

 

그냥 for문으로 1부터 A의 카운트만큼 돌려서 배열에 값이 포함되어있는지 확인하면 안될라나 생각했으나 시간복잡도가 O(n^2)이니 빠른 포기 . . 

 

두 번째 방법을 찾아보자

 

일단 1부터 A의 카운트만큼 집합으로 만들어주고, 배열 A를 집합으로 만들어 subtracting을 한다. 

즉 차집합을 이용하자.

 

알고리즘보다는 그냥 집합의 특징을 이용해 문제를 풀어봅니다. . 

public func solution(_ A : inout [Int]) -> Int {
    let answer = Set(1...A.count).subtracting(Set(A)).sorted()
    if let ans = answer.first {
        return ans
    } else {
        return A.count + 1
    }
}

 

다시 말해 A에 포함되지 않은 숫자를 정렬해주고 최솟값을 가져오는 작업을 처리했습니다.

 

answer에 값이 있다면 정렬된 것의 첫 번째 즉 제일 작은 수를 리턴하고

answer에 값이 없다면 A.count + 1을 리턴하도록 해줍니다.

 

그림으로 예를 들어 A= [1,3,6,4,1,2]이면 함수는 5를 리턴해야 합니다.

왼쪽은 집합화 / 오른쪽은 상관관계

왼쪽 동그라미는 Set(1... A.count)이고 오른쪽은 Set(A)입니다.

위 코드에서 subtracting을 해줌으로 인해 왼쪽에서 오른쪽을 빼줍니다.

 

그럼 결과적으로 5가 남게 됩니다.

answer에는 (5) 값이 존재하니 5를 리턴해주게 됩니다.

// 이 예제는 5만 남게 되었는데 두 개 이상이 남게 될 경우에는 정렬한 것의 첫 번째 값을 가져오면 최솟값을 가져올 수 있습니다. 

 

이렇게 코드를 채점하니

통과 

 

 

 

결과적으로 시간 복잡도는 O(n)이나 O(nlog(n))을 가지게 됩니다.