[Codility] 4. MissingInteger

문제 링크

MissingInteger

문제 요약

정수로 구성된 배열 A가 주어질 때, A에는 포함되어 있지 않은 가장 작은 양의 정수를 반환해라--ㅋ

예시
A = [1, 3, 6, 4, 1, 2] return 5
A = [1, 2, 3] return 4
A = [−1, −3] return 1

요구사항

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]

초기 코드

O(N**2)의 무지성 코드ㅠㅠ

A를 음, 양의 정수로 나눠 각각 음, 양의 배열에 담고
양의 정수에 아무것도 없다면 음의정수만 있다는 말이므로 return 시켰다.
그리고 다시 for로 contains...
O(N**2)은 예상했다..하..ㅎㅎ

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var posArr: [Int] = []
    var negArr: [Int] = []
    var ans = Int()

    A.forEach { //O(N)
        if($0 > 0) {
            posArr.append($0)
        } else {
            negArr.append($0)
        }
    }
    if(posArr.count == 0) {
        return 1
    }

    for i in 1...posArr.count { //O(N)
        if(posArr.contains(i)) {
            ans = posArr[i-1] + 1
            continue
        } else {
            return i
        }    
    }
    return ans
}

완성 코드

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var setNum = Set<Int>(A)
    var ansVal = Int()
    
    for idx in 1...A.count {
        if !setNum.contains(idx) {
            return idx
        } else {
            ansVal = idx + 1
            continue
        }
    }
    return ansVal
}

계속 시간 초과 뜨면서 푸는데 시간 복잡도 검색하면서 풀었는데 두 시간 걸린 거 같다..

Set의 contains 시간 복잡도가 O(1)이라니...
반면 Array는 O(N)

시간 복잡도 정리 한 번 해야겠다..

현타오는 하루다...ㅋㅋㅋㅋ