Lesson3. Time Complexity - TapeEquilibrium

TapeEquilibrium - Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.

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

문제요약

크기가 N인 정수배열 A에서 임의의 정수 P(0<P<N)에 대해, |(A[0] + A[1] + ... + A[P-1]) - (A[P] + A[P+1] + ... + A[N-1])| 의 최소값을 찾아라

Assume that:

N is an integer within the range [2..100,000];

each element of array A is an integer within the range [−1,000..1,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

P를 1부터 옮겨가면서 최소값을 찾는다. A[0]과 A[1]+...+A[N-1]에서 하나씩 진행하면 차는 이전의 차에서 왼쪽으로 이동되는 항목의 2배 만큼 증가하게 된다.(왼쪽에는 추가되고, 오른쪽에서는 제거)