[Codility] Time Complexity - TapeEquilibrium 풀이

예문

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

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:

class Solution { public int solution(int[] 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.

Write an efficient algorithm for the following assumptions:

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

해석

  • 배열 A : N개의 비어있지 않는 정수로 구성
  • 배열 A : 테이프의 숫자
  • P : 임의의 정수, 0 < P < N
  • 테이프 : 비어있지 않는 두 부분으로 나뉨. A[0]
  • 두 부분 : A[1], …, A[P − 1] 와 A[P], A[P + 1], …, A[N − 1]
  • 두 부분의 차이값 : (A[0] + A[1] + … + A[P − 1]) − (A[P] + A[P + 1] + … + A[N − 1])
  • 최소 차이값를 리턴하라!

풀이

  • 이전 요소 + 현재 값의 합 배열 사용 - 이중 for문 피하는데에 중점.
  • (모든요소의 합 - 이전요소까지의 합) - 이전요소까지의 합 = (A[0] + A[1] + … + A[P − 1]) - (A[P] + A[P + 1] + … + A[N − 1])

제약사항

  • N의 범위는 정수 [2..100,000]
  • A의 각 요소의 범위는 정수 [−1,000..1,000]

코드

public int solution(int[] A) {
    int[] sumArray = new int[A.length]; //이전 요소까지의 합 배열
    int length = A.length;

    for (int i = 0; i < length; i++) {
        if (0 == i) sumArray[i] = A[i]; //초기 값 설정
        else sumArray[i] = sumArray[i - 1] + A[i];  //이전 요소와 현재 값 더함.
    }
    boolean isFirst = true;
    int result = 0;
    for (int i = 1; i < length; i++) {  //P는 0 < P < N이므로 1부터 시작
        int sum = (sumArray[length - 1] - sumArray[i - 1]) - sumArray[i - 1];
        sum = Math.abs(sum);
        if (isFirst) {
            result = sum;
            isFirst = false;
        } else result = Math.min(result, sum);
    }
    return result;
}

결과