[Codility] Lesson5.MinAvgTwoSlice (Python)

1. 문제

app.codility.com/c/run/trainingR25CEU-GHW/

Codility

2. 풀이

Timeout Error 시간초과 ㅜ__ㅜ 

결과적으로 slice 크기가 2 또는 3일 경우에만 비교해야한다.

 

(A+B) <= (C+D)일때 (A,B)와 (C,D)의 평균은 (A+B)이상이된다.
따라서 (A,B,C,D)의 평균의 경우 (A,B), (C,D)로 쪼갰을때 각각의 평균값 보다 이상이된다.
원소가 3개인 그룹에서 2개+1개 그룹의 경우를 비교해야하는데 문제에서 한 그룹에 2개 이상의
원소가 있다고했으므로 2개, 3개 그룹만 비교하면 된다.

 

3. 코드

# return the smallest starting position of such a slice.
# average = sum[P:Q]/(Q-P+1)

def solution(A):
    sum = [0] * len(A)
    minval = 99999
    answer = -1

    for i in range(len(A)):
        if i == 0:
            sum[i] = A[i]
        else:
            sum[i] = sum[i-1] + A[i]

    for p in range(len(A)):
        for q in range(p+1, len(A)):
            if p!=0:
                tmpSum = sum[q]-sum[p-1]
            else:
                tmpSum = sum[q]
            res = tmpSum / (q-p+1)
           # print(res)
            if minval > res:
                minval = res
                answer = p

    return answer

처음에 작성했던 코드. 시간초과로 Fail 

# return the smallest starting position of such a slice.
# average = sum[P:Q]/(Q-P+1)

def solution(A):
    minavg = (A[0] + A[1])/2
    answer = 0

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

        avg = (A[i]+A[i-1])/2
        if minavg > avg:
            minavg = avg
            answer = i-1
            
    return answer

 

 

위 풀이에서 말한것과 같이 2, 3 slice일 경우에만 비교를 해준다.

---

✔참고

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

[Codility] MinAvgTwoSlice 문제 풀이 | jcheolho