Codility - MinAvgTwoSlice

20%의 정답률 코드ㅠㅠ

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    # step 1 - input array A
    # already succeed
    tmp = sum(A[0:2])/len(A[0:2])
    
    # step 2 - get the avaerage value in for loop
    A_length = len(A)
    for P in range(A_length):
        for Q in range(P+1,A_length-1):
            arr_ = A[P:Q+1]
            arr_sum = sum(arr_)
            arr_len = len(arr_)
            if tmp >= arr_sum/arr_len:
                tmp = arr_sum/arr_len
                return_value = P
                
    return return_value
    
    pass

 

slice가 몇개까지 쪼개질 지 그 길이를 먼저 구하고 그만큼만 돌리려고 하는 코드는 좋은 접근이었다.

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    # step 1 - input array A
    # already succeed
    
    # step 2 - get a length of slice
    slice_len = len(A)-1
    length = len(A)
    arr = []
    
    for i in range(2,slice_len):
        for j in range(slice_len-i+1):
            arr.append(sum(A[j:j+i])/len(A[j:j+i]))
            print(j,"###",sum(A[j:j+i])/len(A[j:j+i]))
            
    
    
    return min(arr)

    

한개씩 더해가면서 최솟값을 구하려고 하는 접근도 정답률은 좋지 못했지만, 나름 괜찮은 발상이었다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    
    if len(A) == 3:
        return 0
    
    # step 1 - input array A
    # already succeed
    
    length = len(A)-1
    
    X = A[:length-1]
    Y = A[1:length]
    C = [x+y for x,y in zip(X,Y)]
    tmp = min(C)/2
    
    print(C.index(min(C)))
    
    
    return_value_index = C.index(min(C))
    
    
    for i in range(2,length):
        print(i)
        Y = A[i:length]
        print(Y)
        C = [x+y for x,y in zip(C[:length-i],Y)]
        print(C)
        if tmp >= min(C)/i+1:
            tmp = min(C)/i+1
            return_value_index = C.index(min(C))
    
    
    return return_value_index

    

 

 

다양한 시도 끝에 결국 구글의 힘을 빌렸다.ㅠㅠ

 

잘 설명해주신 링크가 있어서 미리 출처를 밝힌다.

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

[Codility] MinAvgTwoSlice 문제 풀이 | jcheolho

 

핵심은 이렇다.

 

 

4개의 원소의 평균은 2개씩 나누어서, 각 (2개의 평균)의 최솟값보다 크다고 한다. 그래서 최솟값이 있는 위치(인덱스)를 구하면 되는 문제였다. 열심히 풀어보았는데 생각보다 정확도가 잘 안되서 화가난다.!!

 

아래는 시간복잡도 O(N)의 100% 정답코드다

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    min_value = sum(A[0:2])/2
    min_index = 0
    for i in range(len(A)):
        try:
            if min_value > (A[1+i] + A[i])/2:
                min_value = (A[1+i]+A[i])/2
                min_index = i
            
            if min_value > (A[2+i] + A[1+i] + A[i])/3:
                min_value = (A[2+i] + A[1+i] + A[i])/3
                min_index = i
        except:
            break
    
    return min_index
    
    pass