[파이썬] Codility - Lesson 3 Time Complexity: TapeEquilibrium

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

TapeEquilibrium coding task - Learn to Code - Codility

문제 간단 해석

정수로 이루어진 list에서 기준점 P를 잡아서,

기준점의 왼쪽, 오른쪽 (기준점 포함) 합의 차가 최소인 경우를 반환하는 문제입니다.

예를 들어

A = [3, 1, 2, 4, 3], P = 3일 경우 (index, 즉 A[3] = 4 기준일 경우)

왼쪽: A[0], A[1], ... A[P-1] -> A[0]+A[1]+A[2] = 6

오른쪽: A[P], A[P+1], ... A[N-1] -> A[3]+A[4] = 7

P = 3일때 차이는 abs(6-7) = 1 입니다.

그 외에

P=1일때 7

P=2일때 5

P=4일때 7 이므로 답은 1이 됩니다.

 

문제 풀이

s = A의 합, m = float('inf') [minimum을 계산하기 위한 임의의 값], left_sum = 0으로 설정해둔 뒤,

for loop를 A[:-1] 만큼 돌려줍니다. 

s = sum(A)
m = float('inf')
left_sum = 0

for i in A[:-1]:

그 후 left_sum에 각 A의 값을 더해주고,

m을 현재의 m값 or abs(s-2*left_sum)) 값 중 더 작은 값으로 설정해둡니다.

s = sum(A)
m = float('inf')
left_sum = 0

for i in A[:-1]:
    left_sum += i
    m = min(abs(s - 2*left_sum), m)

예를 들어

A = [3, 1, 2, 4, 3] 일 경우,

첫번째 A[0] = 3 에서 left_sum 은 3이 되고,

abs(s-2*left_sum)) 값은 abs(13-6) = 7이 됩니다 (P=1일때 7).

이런 식으로 for loop를 끝까지 돌려준 뒤,

최종적으로 m을 반환합니다.

 

전체 코드

def solution(A):
    s = sum(A)
    m = float('inf')
    left_sum = 0
    for i in A[:-1]:
        left_sum += i
        m = min(abs(s - 2*left_sum), m)
    return m