[codility] 풀어보기 - MinAvgTwoSlice

Lesson 5-3 - MinAvgTwoSlice

내용 : Find the minimal average of any slice containing at least two elements.

시간 복잡도 : O(n)

정답 코드는 : 

def solution(A):

    min_avg_value = (A[0] + A[1])/2.0   # The mininal average

    min_avg_pos = 0     # The begin position of the first

                        # slice with mininal average

 

    for index in xrange(0, len(A)-2):

        # Try the next 2-element slice

        if (A[index] + A[index+1]) / 2.0 < min_avg_value:

            min_avg_value = (A[index] + A[index+1]) / 2.0

            min_avg_pos = index

        # Try the next 3-element slice

        if (A[index] + A[index+1] + A[index+2]) / 3.0 < min_avg_value:

            min_avg_value = (A[index] + A[index+1] + A[index+2]) / 3.0

            min_avg_pos = index

 

    # Try the last 2-element slice

    if (A[-1]+A[-2])/2.0 < min_avg_value:

        min_avg_value = (A[-1]+A[-2])/2.0

        min_avg_pos = len(A)-2

 

    return min_avg_pos

출처 : https://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/

풀이 :

• 부분집합은 2의 부분집합, 3의 부분집합에 다 포함되므로 두가지 경우에 대해 비교
• 수학을 알면 쉬운 문제
• 수학모르면  깽판나는 문제
• 아 여러가지로 짜증