codibility - TapeEquilibrium

문제

• Array가 주어졌을 때 0 < p < N의 index 좌우 합 차이 절대값 중 가장 작은 값

내 코드

def solution(A):
    result = 100000000000000000
    
    N = len(A)
    for p in range(1, N):
        diff = abs(sum(A[p:]) - sum(A[:p]))
        if diff < result:
            result = diff
    return result

• ㅋㅋ np.inf 밖에 기억이 안나서 ... 대충 큰 숫자로 ... 앞으론 지양하자
• min 함수로 처리할 수 있는 부분은 굳이 if문 쓰지말고 처리하자
• p로 인한 O(N), sum으로 인한 O(N)으로 총 O(NxN)

지피티 코드

def solution(A):
    total_sum = sum(A)
    min_diff = float('inf')
    left_sum = 0

    for p in range(1, len(A)):
        left_sum += A[p - 1]
        right_sum = total_sum - left_sum
        diff = abs(left_sum - right_sum)
        min_diff = min(min_diff, diff)

    return min_diff

• 기억하자 float('inf')
• 문제의 특성을 잘 파악하자 굳이 오른쪽 (혹은 왼쪽) 의 합을 다시 구할 필요가 없음
  • 이걸로 O(N)으로 줄일 수 있게 됨