[codility] MinAvgTwoSlice

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

MinAvgTwoSlice coding task - Learn to Code - Codility

s[0] =0 s[1]=a[0] s[2]=a[0]+a[1] ...

이렇게 s를 먼저 구해놓고 -> O(N)

p,q를 이중 for문 돌리면 O(N^2)인데 될까.... 응 안됑 60퍼

def solution(A):
    # write your code in Python 3.6
    s = [0]
    tmp=0
    for i in A:
        tmp+=i
        s.append(tmp)

    n = len(A)
    min_val = (A[0]+A[1])/2
    ret = 0
    for p in range(n-1):
        for q in range(p+1,n):
            p_avg = (s[q+1]-s[p])/(q-p+1)
            if min_val > p_avg:
                min_val = p_avg
                ret = p    
    return ret

 

다이나믹!!!으로 해보자

요건 왠지 모르겠지만 시간초과ㅠㅠ

이렇게 하면 문제점이 직전 배열 중에 길이가 3인게 제일 작앗다면(a[q-1],a[q-2],a[q-3])

지금 배열에서 d_a 길이는 4가 되고 (a[q], a[q-1],a[q-2],a[q-3])

a_a는 a[q], a[q-1]이라서 

a[q-1], a[q-2]는 q-1번째에서 고려를 했지만

q번째에서는 a[q], a[q-1], a[q-2] 가 어떻게 되는지 비교할 수 없다

app.codility.com/demo/results/training7XYMA8-BGT/

def solution(A):
    # write your code in Python 3.6
    min_p = 0
    min_q = 1
    min_avg = (A[0]+A[1])/2
    d = [(0,0,0),(min_p,min_avg,A[0]+A[1])]

    for q in range(2,len(A)):
        num_qp = q - d[q-1][0]+1
        d_a = d[q-1][2]+A[q]
        a_a = A[q-1]+A[q]
        if d_a /num_qp < a_a/2 :
            d.append((q-2, d_a /num_qp, d_a))
            if d_a /num_qp < min_avg:
                min_p = q-2
                min_q = q
                min_avg = d_a /num_qp
        else:
            d.append((q-1, a_a/2, a_a))
            if a_a/2 < min_avg:
                min_p = q-1
                min_q = q
                min_avg = a_a/2
    return min_p

 

그래서 q의 위치에서 왼쪽 방향으로 길이가 2인 것과 길이가 3인 것을 비교해야 함.

p,q의 위치만 알면 합과 평균을 바로 구할 수 있으니

avg의 최소일 때 min_avg, min_p, min_q 값만 기억하고 잇으면 되는듯

def solution(A):
    # write your code in Python 3.6
    s = [0]
    tmp=0
    for i in A:
        tmp+=i
        s.append(tmp)

    min_p=0
    min_q=1
    min_avg = (A[0]+A[1])/2

    for q in range(2,len(A)):
        idx_2, idx_3 = q-1, q-2
        avg_2 = sum(A[idx_2:q+1])/2
        avg_3 = sum(A[idx_3:q+1])/3
        if avg_2 < min_avg:
            min_p = idx_2
            min_q = q
            min_avg = avg_2
        
        if avg_3 < min_avg:
            min_p = idx_3
            min_q = q
            min_avg = avg_3
    
    return min_p

 

 

참고

cheolhojung.github.io/posts/algorithm/Codility-MinAvgTwoSlice.html

yeonghyeon.medium.com/codility-lesson-05-3-minavgtwoslice-cdfabd7c4e1a