[C++ 풀이] Codility - Lessons 8 (Leader), Dominator

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

 

 

문제

 

 

 

 

설명

 

 

이 문제는 배열 A가 주어지고, A의 요소들은 -2,147,483,648 ~ 2,147,483,647 사이의 정수로 입력됩니다.

 

이 중 배열 길이의 절반 초과로 나오는 정수가 있을 경우 해당 정수의 Index 값을 반환하면 되고, 없을 경우엔 -1을 반환하면 됩니다.

 

 

예를 들어 위 예제처럼 A의 배열 요소가 주어진다면, 3의 갯수는 5개가 됩니다.

 

배열 A의 길이는 8이고요. 따라서 배열 절반 길이인 4보다 3의 갯수가 더 많음으로,

 

return 값은 0, 2, 4, 6, 7(A배열의 Index값) 중 하나의 값만 return해주면 됩니다.

 

 

 

 

결과

 

#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    map<int, int> m;
    int max = 0, index;
    
    for(int i = 0; i < A.size(); i++){
        if(m.find(A[i]) != m.end())
            m[A[i]] += 1;
        else
            m.insert(pair<int, int>(A[i], 1));
            
        if(max < m[A[i]]){
            max = m[A[i]];
            index = i;
            
            
            if(max > A.size() / 2)
                return index;
        }
        
    }
    
    return -1;
}

 

https://app.codility.com/demo/results/trainingZ988PS-J66/

 

 

저는 map을 이용하여 풀었고, 중복되는 숫자가 나오면 map에 있는 값을 증가시켜 주었습니다.

 

그리고 max값을 이용해 가장 많이 나온 수를 기억하고 해당 index값을 기억한 후 반환하는 식으로 풀었습니다.

 

여기서 중요한 사실은, 중복되는 값의 갯수가 A의 길이를 넘어서는 순간 해당 값은 나올 수 있는 경우의 수는 해당 값만 있으므로 

 

나머지의 갯수를 고려하지 않아도 됩니다.

 

예를들어 A배열의 길이는 10인데, 3의 갯수가 6개면 무조건 3의 index값이 답입니다. 나머지 숫자는 고려 안해도 됩니다. 

 

어쨌든 위 조건을 만족하는 경우의 배열의 절반 길이보다 커야하니깐 말이죠.

(배열길이가 10이고 3의 갯수가 6개인데 4의 갯수가 6 혹은 7개일 수가 없으니깐 말이죠...)