[Swift 알고리즘] Dominator - Codility

Dominator coding task - Learn to Code - Codility

---

의사 코드

 1. leader 후보 찾기
     배열을 탐색하며, size == 0이라며면,
         해당 값을 value에 할당한다. size += 1
     size == 0이 아니라면,
         새로운 값이라면, size -= 1
         새로운 값이 아니라면, size += 1
    
     2. 후보 개수 세기
     candidate = -1
     if size > 0이라면,
         candidate = value
     배열에서 candidate와 같은 값의 index를 저장한다.
     return candidate의 개수 > 배열의 크기 / 2 이면 ? index 배열 : - 1

풀이

import Foundation
import Glibc

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

    for elem in A {
        if size == 0 {
            value = elem
            size += 1
        } else {
            if value != elem {
                size -= 1
            } else {
                size += 1
            }
        }
    }

    var candidate = -1
    var count = 0
    var idxArray = -1
    if size > 0 {
        candidate = value
    }

    for i in 0..<A.count {
        if A[i] == candidate {
            count += 1
            idxArray = i
        }
    }

    return count > (A.count / 2) ? idxArray : -1
}