[Codility] Lesson3- TapeEquilibrium

풀만했던 문제!

처음엔 DP로 풀어야하나 했는데 간단하게 풀리는 문제였다

//P는 0과 N 사이
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        //N=2인 경우, P는 반드시 1
        int N=A.length;
        if(A.length==2)
            return Math.abs(A[0]-A[1]);
        
        //P=1인 경우를 basecase로 둠
        int min=0;
        int fsum=A[0];
        int rsum=0;
        for(int i=1; i<N; i++)
            rsum+=A[i];
        min=Math.abs(rsum-fsum);
         
        for(int i=2;i<A.length; i++){
            //i는 P의 인덱스
            fsum=fsum+A[i-1];
            rsum=rsum-A[i-1];
            if(min>Math.abs(fsum-rsum))
                min=Math.abs(fsum-rsum);
        }
        return min;
        
    }
}

간단한 논리이다.

P는 1부터 N-1까지 이동할 수 있고,

1부터 늘어나는 과정을 생각해보면, P가 늘어날 때 마다 A[P-1]이 앞 파트에 더해지고 뒤파트에서는 빠지게된다.

O(N)포문 두개만 돌리면 문제 해결이 가능하다.