[Swift 알고리즘] Codility demo task

코테 문제 시작 전에 테스트용 문제였는데 나름 잼써서.. ㅎ

원래 문제 풀 생각이 없었어서 대충 보다가 비록 시간 내에 통과하지는 못했지만..? ㅠ 아마도 맞겠지..?

 

Write a function 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.
Biven 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]

import Foundation
import Glibc

pubic func solution(_ A : inout [Int]) -> Int {
    // Implement your solution here
    return 0
}

A 배열 인자 범위는 -100만 ~ 100만. 개수는 10만 이하.

A 배열에 포함되지 않은 가장 작은 양의 정수를 구하는 문제.

1. A가 1을 포함하고 있지 않으면 1을 반환

2. 그 외의 경우 정렬, 중복제거 해준 다음

3. 반복문 돌리기

  3-1. A[i]가 0 또는 음수일 경우, pass

  3-2. A[i]가 양수일 경우 1부터 +1씩 해주며 차례로 확인하기

 

public func solution(_ A: inout [Int]) -> Int {
    if !A.contains(1) { return 1 } //1

    A = Set(A).sorted() //2

    var temp = 1
    for i in 0..<A.count { //3
        if A[i] > 0 {
            if A[i] == temp {
                temp += 1
            } else {
                break
            }
        }
    }
    return temp
}

contains() 도 O(n) 이고 반복문도 O(n)이니까 시간복잡도는 O(n)에 수렴할 것이다. 

정확도는 통과 했을 것 같은데 퍼포먼스 성능 면에서도 통과했을지는 의문.. ㅠ 아쉽다 제대로 풀어볼걸 ㅎㅎ 

 

var arr = [1,3,6,4,1,2] //5
var arr2 = [-1,-2,1,4] //2
var arr3 = [1,2,3] //4

print(solution(&arr))