[Codility Lesson3] Time Complexity_ TapeEquilibrium

문제: TapeEquilibrium

Test results - Codility

 

나의 풀이

- O(N*N)으로 score 53% Performance tests는 0점

- 슬라이싱을 이용하여 품 -> TIMEOUT ERROR

def solution(A):
    # write your code in Python 3.6
    temp = int(1e9)

    for i in range(1,len(A)):
        temp = min(temp,abs(sum(A[:i])-sum(A[i:])))


    return temp

Operation	Example	Class	Notes
Slice	l[a:b]	O(b-a)	슬라이싱되는 요소들 수 만큼 비례

 

 

정답 코드

- 슬라이싱을 사용하지 않고 part를 두개로 나누어 앞파트는 0부터 원소들을 더해가고 뒤파트는 총합에서 원소를 빼간다.

- range 범위를 1부터 시작하여 최소 1번은 나누는 연산으로 설정한다.

def solution(A):
    sum_of_part_one=0
    sum_of_part_two=sum(A)
    min_difference = None
    for i in range(1, len(A)):
        sum_of_part_one+=A[i-1]
        sum_of_part_two-=A[i-1]
        difference = abs(sum_of_part_one -sum_of_part_two)

        if min_difference == None:
            min_difference = difference
        else:
            min_difference = min(min_difference,difference)


    return min_difference