[Swift 알고리즘] EquiLeader - Codility

8. Leader lesson - Learn to Code - Codility

---

문제 분석

 배열을 쪼개, 두 배열 모두 같은 leader를 갖게 하는 index를 모두 return

의사 코드

 leftCount = 0, rightCount = 배열의 길이, leftLeaderCount = 0, rightLeaderCount = 0
 1 .leader 구함
 2. 배열 탐색하면 leader를 만나면
     leftLeaderCount += 1
     rightLeaderCount -= 1
leftSize += 1
rightSize -= 1
leftLeaderCount > leftSize / 2 && rightLeaderCount > rightSize / 2일 때, answer += 1

풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    // leader 구한다.
    let sortedA = A.sorted()
    let candidate = sortedA[A.count / 2]
    var cnt = 0
    for elem in A {
        if candidate == elem {
            cnt += 1
        }
    }
    let leader = cnt > A.count / 2 ? candidate : -1 

    var leftSize = 0
    var leftLeaderCount = 0
    var rightSize = A.count
    var rightLeaderCount = cnt
    var answer = 0

    for elem in A {
        if elem == leader {
            leftLeaderCount += 1
            rightLeaderCount -= 1
        }

        leftSize += 1
        rightSize -= 1

        if leftLeaderCount > leftSize / 2 && rightLeaderCount > rightSize / 2 {
            answer += 1
        }
    }

    return answer
}