[Swift] MissingInteger 문제 풀이 [Codility - Lesson 4. Counting Elements]

💬 문제

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

MissingInteger coding task - Learn to Code - Codility

 

---

💬 Idea

• N 정수의 배열 A가 주어지면 A에서 발생하지 않는 가장 작은 양의 정수(0보다 큼)를 반환해야 하므로
  우선 A를 정렬한 뒤 A에서 1보다 작은 수를 모두 필터링해주었다.
• 이후 결과가 빈 배열이라면 1을 리턴하여 빨리 결과값을 도출해주었고,
• 그렇지 않다면 for문을 돌며 preInteger(이전 정수 값)와 정렬된 원소의 값을 비교하며 그 차이가 1 초과인 경우에 가장 작은 양의 정수를 도출하기 위해 preInteger + 1 을 리턴해주었다.
• 만약 for문을 다 돌고도 가장 작은 정수를 찾지 못했다면 1 이상의 모든 원소가 채워져있는 것이므로
  Set(A)의 개수 + 1을 해서 그 다음으로 작은 수를 리턴해주었다.

 

---

💬 풀이

import Foundation

public func solution(A : inout [Int]) -> Int {
    A = A.sorted()
    A = A.filter({ $0 >= 1 })
    
    if A.isEmpty { return 1 }
    
    var preInteger = 0
    
    for i in A {
        if i - preInteger > 1 {
            return preInteger + 1
        } else {
            preInteger = i
        }
    }
    
    return Set(A).count + 1
}

 

시간 복잡도 : O(N) or O(N * log(N))

https://app.codility.com/demo/results/trainingK7RBSR-4DF/

Test results - Codility

 

 

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Codility/Counting%20Elements/MissingInteger.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift