[Swift] Dominator 코딜리티 코딩테스트

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

 A[0] = 3    A[1] = 4    A[2] =  3
 A[3] = 2    A[4] = 3    A[5] = -1
 A[6] = 3    A[7] = 3
The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

public func solution(_ A : inout [Int]) -> Int

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

 A[0] = 3    A[1] = 4    A[2] =  3
 A[3] = 2    A[4] = 3    A[5] = -1
 A[6] = 3    A[7] = 3
the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

해결방법

배열길이가 0 인경우 dominator가 없으므로 -1 리턴

길이가 1인경우 그자체가 dominator이르모 0을 리턴해준다.

그외에는 다음 로직을 넣어준다.

배열의 값을 키로 그리고 인덱스를 배열에 담아 dictionary를 만들어줬다.

[
	3:[0,2,4,6,7] , 
	4:[1] ,
	-1 : [5],
	2: [3]
]

그리고 만약 dictionary의 valuer값의 길이가

주어진 배열의 반보다 긴 경우

dominator를 찾은것이고 아무 값이나 리턴해주면된다.

만약 못찾았다면 dominator를 못찾은거고 -1 리턴해주면 된다.

public func solution(_ A : inout [Int]) -> Int {
  if(A.count == 0){ return -1}
    if(A.count == 1){ return 0}
    
    var dict = [Int:[Int]]()

    for i in 0..<A.count{
        let value = A[i]
        if(dict[value] == nil){
            dict[value] = [i]
        }else{
            dict[value]!.append(i)
            if(dict[value]!.count>(A.count/2)){return i}
        }
    }
    return -1
}

답은 맞췄으나 시간복잡도가 O(Nlog(N)) or O(N) or O(N**2) 이 나왔다.*