TapeEquilibrium

🔗 문제 링크

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

❔ 문제 설명

A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7

Write a function:

def solution(A)

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

the function should return 1, as explained above.

⚠️ 제한사항

• 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].

---

💡 풀이 (언어 : Java)

처음에 최소값을 잘못 설정해줘서 틀렸고, 그 다음에는 시간 복잡도 $O(N)$으로 목표대로 잘 짠 것 같았지만, 왜인지 시간복잡도에서 0.01초 차이로 탈락했다. Arrays.stream().reduce()를 이용해서 배열 원소들의 총합을 구했는데 이것이 문제였다. 일반 반복문으로 원소 총합을 구하는 것으로 바꿨고 통과했다. 나는 stream이 일반 반복문들보다 빠르다고 여태 알고있었는데, 일반적으로는 stream이 조금 더 느리다고 한다. 대신 가독성이 높아지고 적은 케이스들 중에서는 일반 반복문보다 빠를 수도 있다고 한다.
풀이 포인트는 총합을 미리 계산해서 부분합의 차이만큼 빼주어서 반복문 한번에 해당 인덱스별 두 집단의 원소 총합을 빠르게 계산할 수 있다는 것이다.

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        int arraySum = 0, partSum = 0, min = 1000 * 100000;
        for (int a : A)
            arraySum += a;
        for (int i = 0; i < A.length-1; i++) {
            partSum += A[i];
            int check = Math.abs(2*partSum - arraySum);
            if (check < min) 
                min = check;
        }
        return min;
    }
}