[Swift 알고리즘] MissingInteger - Codility

https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/

---

요약

O(N) or O(N * log(N))

88 → 100

쉬운 문제였다.

첫 번째 풀이에 중복 제거를 고려하지 못 했다.

정답 제출에 조금 더 신중해 보자.

접근

// 문제 분석
// 배열에 없는, 0보다 큰, 가장 작은 정수를 return 하라

// 접근
// 배열 A의 길이는 1...100,000. 따라서 O(N^2) 불가능
// 쉽게 생각나는 방법은 100,000 크기의 check 배열을 생성한 후에, O(N)
    // A를 탐색하며 True로 바꾸고 O(N)
    // 가장 먼저 등장하는 False의 index를 return 하는 것. filter의 시간복잡도? 정렬이 아니고 탐색이니까 O(N)일 듯하다.

// 두 번째 방법은 A 배열을 오름차순으로 정렬하고 O(NlogN)
// 배열을 탐색하며, 1부터 1씩 증가하는 변수와 비교하여, 현재 원소와 일치하지 않는 순간 return. O(N)

// 땡기는 두 번째 먼저 풀어보고, 안 되면 첫 번째로 풀자

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    // 두 번째 방법은 A 배열을 오름차순으로 정렬하고 O(NlogN)
    // 정렬하기 전에 중복 제거를 해주어야 함.
    let sortedA = Array(Set(A)).sorted() // 오름차순
    var counter = 0
    // 배열을 탐색하며, 1부터 1씩 증가하는 변수와 비교하여, 현재 원소와 일치하지 않는 순간 return. O(N)
    for elem in sortedA {
        if elem <= 0 { continue } // 음수는 빼고 count
        counter += 1
        if counter != elem {
            return counter 
        }
    }

    return counter + 1
}