[Codility] Lesson 8 - Dominator

Task discription

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

class Solution { public int solution(int[] A); }

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].

Source code

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int solution(vector<int> &A) {
    int n = A.size();
    if(n == 1) return 0; // 원소가 1개이면 당연히 dominator이므로 return

    // 같은 원소의 갯수를 세기 위해 벡터를 복사해 정렬
    vector<int> tmp;
    for(int i=0;i<n;i++) {
        tmp.push_back(A[i]);
    }
    sort(tmp.begin(), tmp.end());

    int ans = 1e9; // 최댓값 이상으로 초기화

    int cnt = 1;
    for(int i=1;i<n;i++) {
        // 바로 전 원소와 값이 같다면 count+1
        if(tmp[i] == tmp[i-1]) {
            cnt++;
            // 마지막 원소가 전 원소가 같은 경우를 따로 체크해줘야함.
            // ex) 0 0 1 1 1
            if(i == n-1) {
                if(cnt > n/2) {
                    ans = tmp[i-1];
                    break;
                }
            }
        }
        // 바로 전 원소와 같지 않다면 dominator인지 체크
        else {
            if(cnt > n/2) {
                ans = tmp[i-1]; // dominator 값 저장
                break;
            }
            cnt = 1;
        }
    }

    // dominator 값과 같은 원소가 존재하는 위치를 return
    for(int i=0;i<n;i++) {
        if(A[i] == ans) {
            return i;
        }
    }
    return -1;
}

Review

성능 오류날 줄 알고 주먹구구 식으로 풀었는데 의외로 통과한 문제,,
여러가지 예외 처리를 해줘야 100퍼 답을 받을 수 있었다,,