TapeEquilibrium

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

TapeEquilibrium coding task - Learn to Code - Codility

 

codility 문제는 조건을 잘 읽어야 하는 듯..

배열을 P를 기준으로 두 그룹으로 나눴을 때 양 그룹별 합 끼리의 차의 절대값이 가장 작은 값을 찾는 문제다.

이때 P는 0<P<N이고, 두 그룹을 나눴을 때 왼쪽 그룹은 [0]~[P-1] 까지, 오른쪽 그룹은 [P]~[N-1]까지다.

 

부분합을 저장한 배열을 이용했다.

 

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        if (N == 2) return Math.abs(A[1] - A[0]);

        int[] sum = new int[N];
        sum[0] = A[0];
        for (int i = 1; i < N; i++) {
            sum[i] = A[i] + sum[i-1];
        }

        int total = sum[N-1];

        int min = Integer.MAX_VALUE;
        for (int P = 1; P < N; P++) {

            int left = sum[P-1];
            int right = total - sum[P - 1];

            int diff = Math.abs(right - left);

            if (diff < min) min = diff;
        }

        return min;
    }
}

 

부분합 배열을 쓰기 싫다면, P를 옮겨가면서 계산에 사용할 left, right 값을 정의해두고 A[P-1] 값으로 left에 +, right에 - 계산했어도 됐을거 같은데, 배열을 써도 어쨌든 100점 나오니까...