Lesson 8. Leader - Dominator #2

Dominator #1에서는 map을 이용해서 풀었다.

이번에는 정렬을 이용해서 풀어본다.

1. 아이디어

대표값이 되려면 등장 횟수가 배열 크기의 절반을 초과해야 한다.

그렇다면 배열이 정렬되어 있다면? 대표값은 항상 배열의 중간에 위치하고 있지 않을까?

 

예시)

 

정렬 전

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]
3	4	3	2	3	-1	3	3

 

정렬 후

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]
-1	2	3	3	3	3	3	4

 

배열 전체의 절반을 넘게(초과) 차지하려면, 배열 중간값을 항상 대표값이 가지게 되어있다.

 

2. 문제풀이 전략

1. 배열을 정렬한다
2. 배열 중간 값을 대표값으로 정한다
3. 대표값이 배열에 몇 번 등장하는지 확인한다. (배열 전체탐색)

 

3. 코드 (C++)

int solution(vector<int> &A) {

    if(A.empty()) return -1; //빈 배열

    //정렬
    vector<int> temp = A;
    sort(temp.begin(), temp.end());

    //대표값 선정
    int half_idx = temp.size() / 2;
    int dominator = temp[half_idx];
    
    //대표값 등장 횟수 세기(전체탐색)
    int cnt = 0;
    for(size_t i = 0; i < A.size(); i++)
    {
        if(A[i] == dominator) cnt++;
    }

    //대표값이 등장 횟수 조건을 충족하는지 확인
    if(cnt <= A.size() / 2) return -1;

    auto it = find(A.begin(), A.end(), candidate);
    int idx = distance(A.begin(), it);
    
    return idx;
}

 

 

4. 결과