[codility] TapeEquilibrium (java)

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

TapeEquilibrium coding task - Learn to Code - Codility

코딜리티 lesson 3의 TapeEquilibrium라는 문제입니다.

문제는 대략 이렇습니다. 특정 배열의 원소를 => 두 그룹으로 나누었을 때 나뉜 두 그룹의 차이에 대한 절댓값이 가장 작은 경우를 구하는 문제입니다. 말이 조금 추상적이기 때문에 예시를 가지고 설명드리겠습니다.

예를 들면 A라는 배열의 원소와 값이 아래와 같이 있습니다.

• 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

p가 1이면  1번째 원소(=0번째 인덱스 )  /  2~5번째 원소(1~4인덱스)로 나누고

각 그룹의 합을 구해서 뺸다음에   그 값의 절댓값 한 값을 구하는 문제입니다.

위 경우에서 P가 3일 때 1이 가장 작은 경우 이므로 정답은 1이 됩니다.

풀이

최소 값을 구하기 위한 min이라는 변수, 왼쪽 값을 구하기 위한 변수, 오른쪽 값을 구하기 위한 변수를 선언하였습니다.

이제 관건은 왼쪽과 오른쪽 값에 대한 규칙을 구해야 되는데요 (왼쪽 오른쪽 이란 |left - right|  를  의미합니다.)

왼쪽 값의 규칙 : 1번 원소부터 P까지의 합

오른쪽 값의 규칙 : 전체 값 - 왼쪽 값임을 발견하였습니다.

public class TapeEquilibrium {
    public static void main(String[] args) {
        TapeEquilibrium tapeEquilibrium = new TapeEquilibrium();
        int[] arr = {3, 1, 2, 4, 3};
        System.out.println(tapeEquilibrium.solution(arr));
    }

    public int solution(int[] A) {
        int min = Integer.MAX_VALUE;
        int right = 0;
        int left = 0;

        for (int a : A) {
            right += a;
        }

        // 맨 마지막 원소는 두 배열로 나누었을때 남겨야 하므로 length -1
        for (int i = 0; i < A.length - 1; i++) {
            right -= A[i];
            left += A[i];
            min = Math.min(min, Math.abs(left - right));
        }
        return min;
    }
}