Codility Lesson 03 - TapeEquilibrium( JAVA )

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

TapeEquilibrium coding task - Learn to Code - Codility

문제

- 배열 A는 비어있지 않고, N개의 정수( Integer )로 되어있다.( 배열 A는 테이프 위의 수들이다 )

- 0 < P < N의 P는 테이프를 비어있지 않은 2개의 배열로 분할한다.( A[0] ~ A[P-1] / A[P] ~ A[N-1] )

- P의 범위 안에서 분할된 첫번째, 두번째 부분배열의 합의 차의 절댓값들 중 최소값을 찾아라.

-예시

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

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

- 제한조건

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

N은 2 ~ 100,000 범위안의 수이다.

A배열의 각각의 원소는 -1,000 ~ 1,000 사이의 수이다.

 

풀이

- 전체합을 먼저 구한다.( totalSum )

- for문으로 P범위의 index를 반복, 분할된 첫번째 부분배열의 합( firstSum )을 구하여 | totalSum - firstSum * 2 | 로 answer변수와 비교하며 최소값을 찾는다.

-> totalSum은 ( firstSum + secondSum )임을 착안하여 위와 같은 식으로 풀이

- firstSum은 다음 index가 진행될 때 해당하는 배열의 원소를 +하여 누적하여 구한다.

 

// 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) {
        // write your code in Java SE 8
        int totalSum = 0;
        int firstSum = 0;
        int answer = Integer.MAX_VALUE;
        int tmpSum = 0;

        // 1. 전체 합 구하기
        for( int i:A ) {
            totalSum += i;
        }

        // 2. P범위 만큼 인덱스 반복
        for( int i=1; i<A.length; i++ ){
            firstSum += A[i-1];
            tmpSum = Math.abs(totalSum - firstSum * 2);
            if( tmpSum < answer ){
                answer = tmpSum;
            }
        }

        return answer;
    }
}

- P범위만큼 인덱스 반복 시킬 경우 i값 범위 주의 -> firstSum에 1개 전의 배열값을 누적합시킴으로 i는 1 ~ A.length까지의 범위를 지정