[Swift 알고리즘] Codility - MissingInteger

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "Codility - MissingInteger" 문제를 풀었습니다.

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

MissingInteger coding task - Learn to Code - Codility

 

풀이

이번 문제는 Array에 존재하지 않는 최소 양수를 찾는 문제입니다.

데모 문제라고 써있는 걸 보니 쉬운 난이도같은데 왜 Medium인건지... ㅎ.. (그렇다고 어려운건 아니었음)

 

문제에 non-empty 배열이라고 써있지 않아 빈 배열에 대해 예외처리를 먼저 했습니다.

음수로만 구성된 배열도 예외처리를 했습니다.

 

그 뒤에 배열에서 양수를 걸러내고 sorted( ) 합니다. 

filter는 O(N)이지만 for보다 1.2배정도 더 오래 걸립니다. 하지만 가독성이 훨씬 좋아 filter를 사용했습니다.

 

count 변수를 이용해 연속된 수인지 빠진 수가 있는지 체크합니다.

만약 빠진 수가 있다면 반복을 종료하고 return 합니다.

 

전체 코드

import Foundation

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)

    if A.isEmpty || A.max()! <= 0 {
        return 1
    }

    let A = A.filter { $0 > 0 }.sorted() //O(N) + O(NlogN)

    var count = 1
    for num in A { //O(N)
        if num > count {
            break
        } else {
            count = num + 1
        }
    }

    return count
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.