[Algorithm/Swift] Codility / Dominator

문제

https://app.codility.com/programmers/lessons/8-leader/dominator/

풀이

주어진 배열에서 절반 이상의 과반을 차지하는 동일한 수를 찾습니다. (대표 수)

만약 대표수가 없으면 -1을 리턴합니다.

대표수가 있다면 해당 수의 배열 인덱스를 리턴합니다.

Dictionary를 써서 대표자를 찾습니다.

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

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

    for candidate in A {

        if candidates[candidate] == nil {
            candidates[candidate] = 1
        } else {
            candidates[candidate]? += 1
        }
    }

    let halfOfArray = Int(Float(A.count) * 0.5)
    
    var dominator = 0
    var dominatorCount = 0
    
    for (key, count) in candidates {
        if count > halfOfArray {
            dominator = key
            dominatorCount = count
        }
    }
    
    guard let dominatorIndex = A.firstIndex(of: dominator),
          halfOfArray < dominatorCount else {
              return -1
          }
    
    
    return dominatorIndex
}