[C++ 풀이] Codility - Lessons 5, (Prefix Sums) MinAvgTwoSlice

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

https://www.codility.com/

 

 

 

문제.

 

 

 

설명

 

대충 설명하자면 이렇습니다.

 

1. 정수가 저장된 N개의 배열을 준다.

2. N개의 배열에는 임의의 정수가 있으며 범위는 -10,000 ~ 10,000이다.

3. 이 배열 요소 중 2개 이상의 합의 평균 값 중 가장 작은 평균 값이 시작되는 index 번호를 구하라!!

 

예를 들어 

 

A [0] = 4

A [1] = 2 A [2] = 2 A [3] = 5 A [4] = 1 A [5] = 5 A [6] = 8

 

이 있다고 가정할 때

 

가장 작은 평균 값은 A[1] + A[2] 입니다.

 

이 때 시작하는 index값인 1을 반환해 줘야 합니다.

 

다른 예를 들어보겠습니다.

 

A [0] = 4

A [1] = 8 A [2] = 2 A [3] = 5 A [4] = 1 A [5] = 5 A [6] = 8

 

일 때 가장 작은 평균 값은 A[2] + A[3] + A[4]가 되므로

 

시작하는 index 값인 2를 반환해 줘야 합니다.

 

 

 

 

6시간 동안 고민하다가 풀이방법을 찾아서 풀었습니다.

 

하지만 풀이를 봐도 이해가 가질않아..... 수학을 잘하는 친구에게 물어봤고 어느정도 이해는 했습니다.

(수학 잘하는 사람은 쉽게 푼다는 말이 사실이었네요.....)

 

 

 

풀이를 말씀드리자면....

 

1. 검색할 범위, 중복 숫자, 음수 양수를 고민할 필요가 없다.

2. 무조건 2개 혹은 3개의 범위를 묶어 평균 값을 비교하면 된다.

3. 3개를 묶는 이유는 경우의 수는 드물지만 2번째 예제처럼 3개의 평균 값이 낮을 경우가 있어서.

4. 4개 범위 이상은 무의미하다.

 

이하 코드를 보시면 한번에 이해가 가실 겁니다.....

 

 

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.size() < 2) return 0;

    int index = 0;
    double min = (A[0] + A[1]) / 2;
    double two_avg = 0, three_avg = 0;


    for(int i = 2; i < A.size(); i++){

        three_avg = (A[i - 2] + A[ i - 1] + A[i]) / 3.0;
        two_avg = (A[ i - 1] + A[i]) / 2.0;

        if(two_avg < min){
            min = two_avg;
            index = i - 1;
        }
        if(three_avg < min){
          min = three_avg;  
          index = i - 2;
        } 

    }

    return index;
}
​

 

 

https://app.codility.com/demo/results/training4MH4EY-ZHB/

 

 

 

 

하... 수학 싫다.....