코딜리티 Time Complexity - TapeEquilibrium (파이썬)

Time Complexity - TapeEquilibrium

 

* 프로그래밍 주안점

1. 가독성

2. 성능

 

문제링크: https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

 

설명 (요약)

A 리스트 내 왼쪽데이터, 오른쪽데이터의 각각 합을 뺀 절대값이 가장 작은 경우를 찾아라 예: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3 P = 1, difference = |3 − 10| = 7 P = 2, difference = |4 − 9| = 5 P = 3, difference = |6 − 7| = 1 P = 4, difference = |10 − 3| = 7 결과: 1

 

풀이전략

• 입력받는 데이터를 두부분으로 나눈다. 왼쪽부터 더하는 부분 + 오른쪽부터 더하는 부분. 각각 A, B 라고 생각한다.
• |A의합 - B의합| 으로 계산을 수행한다. 
• 루프를 돌며 최소값이 가장 작은 부분을 찾는다.

 

고려사항

• 2개의 항만 존재하는 경우의 처리
• 항상 왼쪽항과 오른쪽 항을 다 더해서 할 경우 O(NxN) 이 되어 타임아웃이 된다.
• 리스트 내 모든 항에 음수가 없다면 최소값이 커질때 중지하면 되지만, 항 중 음수가 있다면 루프를 다 돌아야 한다.

 

코드

 

INF = int(1e9)		# 큰값을 나타내기 위함

def solution(A):
    sum1 = 0			# 왼쪽부터 더하는 리스트의합
    sum2 = sum(A)		# 오른쪽부터 더하는 리스트의합
    min_v = INF

    for i in range(1, len(A)):		# 항목중 음수가 있을수 있기에 모든 항목을 다 조회한다.
        sum1 += A[i-1]
        sum2 -= A[i-1]
        t_v = abs(sum1 - sum2)
        if min_v > t_v:				# 계산식이 가장 작은 값을 찾는다.
            min_v = t_v

    return min_v


solution([3,1,2,4,3])       # return 1
#solution([3,1])            # return 2

 

 

Github: https://github.com/oksk1111/algorithm_python/blob/main/codility_TimeComplexity_TapeEquilibrium.ipynb

GitHub - oksk1111/algorithm_python

 

 

결과

 

Analysis

Detected time complexity: O(N)