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

 

 

 

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

https://www.codility.com/

 

 

 

 

 

 

문제

 

 

 

 

 

 

설명

 

 

이 문제는 생각보다 이해하는데 어려움이 있습니다. 똥같은 문제....

 

이 문제에 대한 설명은 다음과 같습니다.

 

배열 A가 주어지고 배열 A의 요소는 -1,000,000,000 ~ 1,000,000,000 이고 배열의 길이는 1 ~ 100,000 입니다.

 

여기서 리더를 뽑아야 하는데 해당 리더는 2가지 조건이 있습니다.

 

1. 가장 많이 중복되는 값.

2. 배열 길이의 절반 값보다 더 많이 나오는 경우.

 

위 두가지를 만족해야 해당 요소를 리더라고 칭합니다.

 

 

문제의 예제에서 보면 4가 리더입니다.

 

마지막으로 문제에서 원하는 return 값은 배열을 1 ~ N개로 쪼갰을 때 해당 리더 값이 많은 경우의 수를 return 하는 것입니다.

 

길게 설명하자면 다음과 같습니다.

 

A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

 

 

1.

A[0] = 4                     (A[0] 범위 에선 4값이 제일 많음으로 OK)

A[1 ~ 5] = 3, 4, 4, 4, 2  (A[1 ~ 5] 범위 에선 4값이 제일 많음으로 OK)

두 조건 모두 만족함으로 OK.

 

2.

A[0 ~ 1] = 4, 3        (A[0 ~ 1] 범위 에선 4값이 제일 많지 않음으로 Fail)

A[2 ~ 5] = 4, 4, 4, 2  (A[2 ~ 5] 범위 에선 4 값이 제일 많음으로 OK)

두 조건 불만족 함으로 Fail.

 

3. 

A[0 ~ 2] = 4, 3, 4    (A[0 ~ 2] 범위 에선 4값이 제일 많음으로 OK)

A[3 ~ 5] = 4, 4, 2    (A[3 ~ 5] 범위 에선 4값이 제일 많음으로 OK)

두 조건 모두 만족함으로 OK.

 

4. 

A[0 ~ 3] = 4, 3, 4, 4    (A[0 ~ 3] 범위 에선 4 값이 제일 많음으로 OK)

A[4 ~ 5] = 4, 2          (A[4 ~ 5] 범위 에선 4 값이 제일 많지 않음으로 Fail)

두 조건 불만족 함으로 Fail.

 

5.

A[0 ~ 4] = 4, 3, 4, 4, 4    (A[0 ~ 4] 범위 에선 4값이 제일 많음으로 OK)

A[5] = 2                      (A[5] 범위 에선 4값이 제일 많지 않음으로 Fail)

두 조건 불만족 함으로 Fail.

 

 

따라서 두 조건을 모두 만족하는 경우는 2가지 이므로 2를 return 해주면 됩니다.

 

 

 

 

 

결과

 

// you can use includes, for example:
#include <map>
#include <iostream>
// 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, result = 0, count = 0;
    
    for(int i = 0; i < A.size(); i++){
        if(m.find(A[i]) != m.end()){
            m[A[i]] += 1;
            if(max < m[A[i]]){
                max = m[A[i]];
                index = A[i];   
            }
        }else
            m.insert(pair<int, int>(A[i], 1));
    }
    
    if(max < A.size() / 2)
        return 0;
    
    for(int i = 0; i < A.size(); i++){
        if(A[i] == index){
            count++;
            m[index]--;
        }
        
        if(m[index] > (A.size() - (i + 1)) / 2 && count > (i + 1) / 2)
            result++;
        
    }
    
    return result;
}

 

 

 

 

 

https://app.codility.com/demo/results/training5RNWJX-KBR/

 

 

 

해당 문제는 Dominator 문제에서 푼 방법으로, 먼저 리더 값을 찿았습니다.

 

그 후 배열 A[]요소와 리더 값을 비교해 리더 값이 더 많은지 체크를 했습니다.

 

여기서 count 값은 앞부분의 리더 값 갯수고 m[index] 값은 뒷부분의 리더 값 갯수입니다.

 

 

이런식으로 구했기 때문에 result값이 증가되는 조건이 33행처럼 나오게 된 것입니다.