Lesson 3: Complexity → Tape Equilibrium

문제

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

배열에 다섯개의 값들이 있으면 각 구간 별로 나누어 값을 합산 후에 차를 계산하여 가장 작은 차가 되는 값을 찾는 문제이다.

문제 풀이

처음에는 list를 슬라이싱하여 문제에 접근하였다. 슬라이싱으로 인한 오버헤드가 그렇게 큰지는 처음 알았다.

def soultion(A):
    min_diff = None

    for i in range(len(A) - 1):
        diff = abs(sum(A[:i + 1]) - sum(A[i + 1:]))

        if min_diff is None:
            min_diff = diff
        else:
            min_diff = min(min_diff, diff)

• 최초에 작성한 코드는 복잡도가 N^2이어서 테스트 케이스를 통과하지 못한다.

코드

def solution(A):
    left = 0
    right = sum(A)
    min_diff = None

    for i in range(1, len(A)):
        left += A[i - 1]
        right -= A[i - 1]
        diff = abs(left - right)

        if min_diff is None:
            min_diff = diff
        else:
            min_diff = min(min_diff, diff)

    return min_diff

• 리스트를 슬라이싱 하는 것이 아닌, 최초에 합을 구해두고 left에는 값을 더하고, right에는 값을 빼주어 가장 작은 diff를 찾도록 한다.
  • 이 경우 시간 복잡도는 N이다.