[python] Codility Lesson 5-3. MinAvgTwoSlice

 

 

1. for문 2개 돌려 O(N^2) 알고리즘이지만, 막상 그림이 안떠올라 작성해보았다. (60점, performance 0점)

 

def solution(A):
    min_average = 99999
    for i in range(len(A) - 1):
        sum = A[i]
        for j in range(i + 1, len(A)):
            sum += A[j]
            average = sum /(j-i+1)
            if min_average > average:
                min_average = average
                start_index = i
    return start_index

 

1. 최소값을 큰 수로 놓고, 첫번째 for문에서 0 부터 len(A) - 1 까지 즉, start_index 각각의 min_average를 구한다.

 

2. 두번째 for문에서 0-1, 0-4 ... 0 - len(A)-1,  3-5 ... 4-5... N-N+T 모든 min_average를 구하고, start_index값을 할당한다.

 

 

 

 

2. 다른 분 푼 코드 참조 (출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=alwlren_00&logNo=221603639510)

 

a < b < c < d 일 때 a < (a+b)/2 < b 그리고 c < (c+d)/2 < d 이고 (a+b)/2 < (c+d)/2 이니까

결과적으로 (a+b)/2 < (a+b+c+d)/4 < (c+d)/2 임..

3인경우도 생각해줘야하는게 (2,8,2) 은 4, (2,8) = 5 (8,2) = 5 이니까.. 크기 2인경우보다 3이 작을수도 있음.

크기가 4 이상인 부분집합의 평균 들은 크기가 2, 3인 부분집합의 평균보다 클수가 없다! 를 전재로

A의 크기가 2,3인 슬라이스만 비교해주면 되는거였다.

 

정령 이런 수학적 지식이 없다면 풀 수 없는 문제인가 ㅠㅠ

 

def solution(A):
    minAvg = (A[0]+A[1])/2
    result = 0
    for i in range(0, len(A)-1):
        avg = (A[i]+A[i+1])/2
        if minAvg > avg :
            minAvg = avg
            result = i

    for j in range(0, len(A)-2):
        avg = (A[j]+A[j+1]+A[j+2])/3
        if minAvg > avg :
            minAvg = avg
            result = j
    return result