[ Codility ] MinAvgTwoSlice - python

개념

Lesson 5. Prefix Sums 세 번째 문제

 

문제요약

n개의 원소를 갖는 리스트가 주어지면,  0부터 n-1사이에서 두 수를 뽑아 작은 값(P)를 시작인덱스, 큰 값(Q)를 끝인덱스로 정해 A[P:Q+1]에 해당하는 리스트를 슬라이스라고 한다. 만들 수 있는 모든 슬라이스 중 슬라이스 내부 원소들의 평균이 가장 낮을때의 P값(시작인덱스)를 리턴.

 

첫 번째 접근(효율성 고려X)

def solution(A):
    n = len(A)
    min_v = sum(A)/n
    r = 0
    comb = [(i,j) for i in range(n-1) for j in range(i+1,n)]
    for pair in comb:
        new_v = sum(A[pair[0]:(pair[1]+1)])/(pair[1]-pair[0]+1)
        if new_v < min_v:
            min_v = new_v
            r = pair[0]
    return r

문제에 아주 충실하게 구현만 한 코드로, 모든 슬라이스 (시작idx,끝idx)의 조합을 구한 뒤 해당 슬라이스 평균과 최소평균을 비교한 뒤 갱신하는 작업

당연시 시간초과. 이미 조합에서 n**2 => 이걸 다시 돌면서 n번만큼 sum => n**3 이 나온 듯 하다.

 

두 번째 접근(효율성 고려△)

모든 슬라이스마다 sum 작업을 하지않으려면, 처음에 합을 다 더한뒤에 계속 앞에서부터 한번씩 값을 빼주는 방법으로 속도를 올려보려는 생각 (하지만 for문을 2번 돌기때문에 O(n**2) 이상)

def solution(A):
    n = len(A)
    v = sum(A)
    min_v = v/n
    r = 0
    for i in range(n-1):
        new_minv = v/(n-(i+1)+1)
        cnt = n-2
        tmp = v
        while cnt>i:
            tmp -= A[cnt+1]
            if new_minv> tmp/(cnt-i+1):
                new_minv =  tmp/(cnt-i+1)
            cnt -= 1
        if min_v>new_minv:
            min_v = new_minv
            r = i
        v -= A[i]
    return r

정리해보자면

1. 원소개수를 n,n-1,n-2 ... 2개만큼 가지는 슬라이스를 만드는 for문 
2. 각 for문 내부에서 다시 원소개수를 1,2,...,n-2개까지 줄여나가는 while문
3. 최소를 갱신해주는 작업들

이런 느낌으로 구현했지만, 코드가 복잡해서 좋지 않다

보다시피 10%만 개선되었으므로, 결과도 별로 안좋다

 

정답코드

도저히 혼자 고민해서 풀진 못할 것 같아서 결국 구글링. 알고보니 수학을 조금 아는 분들은 쉽게 풀 수 있는 원리(?)가 있는 문제였다.

x,y의 평균 = x,y중 작은 수보다 크고 큰수보다 작은 값(만약 x=y라면 평균은x)

두 수에만 적용되는게 아니라, 여러 수의 그룹도 마찬가지

a,b,c,d의 평균은 a,b의 평균과 c,d의 평균 중 작은 값보다 크고 큰 값보다 작음

결국 이 문제는 작은 수의 그룹의 평균 중 최소만 찾으면 됨(슬라이스 원소의 개수가 2개 혹은 3개일때)

def solution(A):
    min_v = (A[0]+A[1])/2
    result = 0
    for i in range(2,len(A)):
        tmp2 = (A[i-1]+A[i])/2
        tmp3 = (A[i-2]+A[i-1]+A[i])/3
        if tmp2 < min_v:
            min_v = tmp2
            result = i-1
        if tmp3 < min_v:
            min_v = tmp3
            result = i-2
    return result

 

총평

너무 안풀리면 시간 낭비하지말고, 적당히 넘어갈 필요도 있다. 지금의 머리로는 풀 수 없는 문제들을 보내주는 미덕...