[Codility] 코딜리티 5-3. MinAvgTwoSlice (Python)

이전 코드 내용이 궁금하시다면 아래 링크로 이동하시면 됩니다!

코딜리티 이전 글 - 2020/08/06 - [데이터 분석/파이썬] - [Codility] 코딜리티 5-2. GenomicRangeQuery (Python)

[Codility] 코딜리티 5-2. GenomicRangeQuery (Python)

---

1. 문제 설명

• A 에는 N integers들로 구성되어 있습니다.
• 0<=P<Q<N 이라는 규칙 안에서 (A[P]+A[P+1]+...+A[Q])/(Q-P+1)값을 최소로 만드는 P값을 출력하는 문제입니다.

2. 1차 풀이

• idea : min_slice를 크게 잡고, for문 2개를 돌려서 처음부터 끝까지의 경우의 수를 확인해서 최소값이였을 때의 i를 출력

def solution(A):
    min_Slice = 10000
    for i in range(len(A) - 1):
        sum_Slice = A[i]
        for j in range(i + 1, len(A)):
            sum_Slice += A[j]
            average_Slice = sum_Slice/(j-i+1)
            if min_Slice > average_Slice:
                result = i
                min_Slice = average_Slice
    return result

3. 1차 결과 (시간복잡도 : N**2)

1차 테스트 결과

4. 2차 풀이

• idea : 4개항의 최소값은 무조건 2개항의 최소값보다는 크거나 같게 나오게 된다. 그래서 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

5. 2차 결과 (시간복잡도 : N)

2차 결과