/ ALGORITHM

(codility with python) TapeEquilibrium


lesson3 - TapeEquilibrium

https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

O(n^2)의 시간복잡도
list slice 후 sum()을 통해서 합계를 구하는 부분이 o(n^2)의 시간복잡도를 갖는다

def solution(A):
    cand = []
    for i in range(1, len(A)):
        a_sum, p_sum = 0, 0
        a_sum = sum(A[0:i])
        p_sum = sum(A[i:])
        
        cand.append(abs(a_sum - p_sum))
        
    return min(cand)


주의할 점

  • list slice를 사용하지 않는다
  • A[i - 1]은 for문을 통해서 구한다
  • A[P] ~ A[N - 1]은 sum(A)에서 A[i - 1]을 빼서 구한다

O(n)의 시간복잡도

def solution(A):
    a_sum = 0
    p_sum = sum(A)
    m = None
    
    for i in range(1, len(A)):
        a_sum += A[i - 1]
        p_sum -= A[i - 1]
        diff = abs(a_sum - p_sum)
        if m == None:
            m = diff
        else:
            m = min(m, diff)
    
    return m
        
solution([1, 2, 3, 4, 2] )