Codility Lesson 3-3 TapeEquilibrium (python)

solution

처음 푼 문제는 시간 초과 문제가 있었다.

• Detected time complexity : O(N * N)
• list slice 후, sum() 을 통해서 합계를 구하는 부분이 O(N^2)의 시간 복잡도를 가진다.

def solution(A):
    # write your code in Python 3.6
    dif = float('inf')
    for p in range(1, len(A)):
        first = sum(A[:p])
        second = sum(A[p:])
        dif = min(dif, abs(first-second))
    return dif

correct solution

• list slice를 사용하지 않는다
• Detected time complexity: O(N)
• 시간 복잡도 유의

def solution(A):
    # write your code in Python 3.6
    dif = float('inf')
    first = 0
    second = sum(A)
    for p in range(len(A)-1):
        first += A[p]
        second -= A[p]
        dif = min(dif, abs(first-second))
    return dif