Lesson 5: Prefix Sums → Min Avg Two Slice

문제

https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/

MinAvgTwoSlice coding task - Learn to Code - Codility

문제를 보면 모든 구간에 대해 평균을 구해야 할 것 같다. 하지만 모든 구간에 대한 평균을 구할 경우 효율성 부분을 통과하지 못하여 점수를 받지 못한다. 서브 그룹에서 평균을 구할 때의 특성을 활용할 경우 문제를 쉽게 해결 할 수 있으나 그렇지 않을 경우는 풀지 못한다.

---

문제 풀이

예를 들어 수가 4, 2, 2, 5가 있을 경우 각 구간에 대한 평균을 구한다고 가정하자

1. 구간이 2인 경우

   1. (4 + 2) / 2 = 3

   2. (2 + 2) / 2 = 1

   3. (2 + 5) / 2 = 3.5

2. 구간이 3인 경우

   1. (4 + 2 + 2) / 3 = 2.67 (반올림)

   2. (2 + 2 + 5) / 3 = 3

3. 구간이 4인 경우

   1. (4 + 2 + 2 + 5) / 4 = 3.25

위의 예는 구간이 2, 3인 경우만 확인하면 더 이상의 구간을 확인하는 것은 무의미하다는 성질을 보여주는 간단한 예시이다. 

 

---

코드

def solution(A):
    min_avg = (A[0] + A[1]) / 2
    min_idx = 0

    for i in range(2, len(A)):
        avg = (A[i - 2] + A[i - 1] + A[i]) / 3
        if min_avg > avg:
            min_avg = avg
            min_idx = i - 2

        avg = (A[i - 1] + A[i]) / 2
        if min_avg > avg:
            min_avg = avg
            min_idx = i - 1

    return min_idx

• 구간 2, 3에 대한 평균 중 가장 작은 값에 대해 찾고 시작 지점(min_idx)를 유지한 후 반환하면 된다.