[Codility] Lesson 3 : TapeEquilibrium - JAVA

문제

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].
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A)에 입력되는 배열 A는 비어있지 않으며 2 ~ 100,000개의 요소를 가질 수 있고,
배열 A의 요소에는 -1,000 ~ 1,000까지 들어갈 수 있다.

배열 A가 주어졌을 때 임의의 수 P를 기준으로 배열을 나눌 수 있는다. (P는 0보다 크고 배열의 길이보다 작다.)
만약 배열의 길이가 5이고 P가 2이면 A[0], A[1]를 하나의 파트로 구분하고
A[2], A[3], A[4]를 다른 파트로 구분할 수 있다.
이때 나누어진 두 파트 값의 차이를 구해준다.

예를 들어 배열 A를 다음과 같이 작성했을 때,
        A[0] = 3
        A[1] = 1
        A[2] = 2
        A[3] = 4
        A[4] = 3

P = 1이면 (A[0]) - (A[1] + A[2] + A[3] + A[4]) = |3 − 10| = 7
P = 2이면 (A[0] + A[1]) - (A[2] + A[3] + A[4]) = |4 − 9| = 5
P = 3이면 (A[0] + A[1] + A[2]) - (A[3] + A[4]) = |6 − 7| = 1
P = 4이면 (A[0] + A[1] + A[2] + A[3] ) - (A[4]) = |10 − 3| = 7

위의 예시와 같이 임의의 숫자 P에 대해 나눈 배열은 각각 7, 5, 1, 7의 차이가 난다.
이때 가장 작은 값을 찾아 반환한다.

 

풀이 - 1

class Solution {
    public int solution(int[] A) {
        int min = Integer.MAX_VALUE;
        for(int i=1; i<A.length; i++) {
            int frontSum=0, backSum=0;
            for(int j=0; j<i; j++) {
                frontSum += A[j];
            }
            for(int k=i; k<A.length; k++) {
                backSum += A[k];
            }
            min = Math.min(min, Math.abs(frontSum-backSum));
        }
        return min;
    }
}

 

'풀이 - 1'에 대한 회고

 

역시 가장 먼저 생각해볼 수 있는 알고리즘은 반복문을 이용하는 것!

첫 번째 반복문을 통해 임의의 P 값을 가져온다.

그리고 임의의 P 값을 기준으로 index가 P보다 작은 배열의 요소들을 더하고,

index가 P와 같거나 큰 배열의 요소들을 더한다.

그리고 두 값의 차이를 절대값으로 계산하는 동시에 최소값인지 계산해준다.

 

이렇게 작성한 점수는 53%!

 

 

계산 결과는 정확하지만 퍼포먼스가 1도 안나온다!

당연히 반복문이 중첩되어있기 때문에 배열의 길이가 커지면 커질수록

계산하는데 오래 걸리기 때문이다.

 

 

그렇게 나온 시간복잡도는 O(n*n).

이중 for문이 아닌 다른 방법으로 다시 생각해보자!

 

풀이 - 2

class Solution {
    public int solution(int[] A) {
        int total = 0;
        for(int subA : A) {
            total += subA;
        }
        
        int min = Integer.MAX_VALUE;
        int sum = 0;
        for(int i=0; i<A.length-1; i++) {
            sum += A[i];
            min = Math.min(min, Math.abs(total - sum - sum));
        }
        return min;
    }
}

 

'풀이 - 2'에 대한 회고

 

반복문을 두번 사용해도 상관없다.

다만, 이중 for문을 이용하면 '풀이 - 1'의 시간복잡도가 나오기 때문에 퍼포먼스에서 무조건 0점 나온다.

이번에는 배열 전체의 합계부터 구하고 반복문을 통해 차이를 구했다.

여기서 포인트는 'total - sum - sum'!

왜 전체 합계에서 sum을 두 번이나 빼줬을까?

 

문제에서는 임의의 수 P를 기준으로 A[0]부터 A[P-1]까지의 합계와 A[P]부터 A[N]까지의 합계를 구했다.

여기서 sum은 A[0]부터 A[P-1]까지의 합계를 의미한다.

그리고 나머지 합계는 전체 합계에서 sum을 빼면 자동으로 계산된다.

즉, 편의상 나머지 합계를 R이라고 했을 때 R = total - sum이 되는 것이다.

(당연히 A[P]부터 A[N]까지의 합계를 구하기 위해 반복문을 실행할  필요가 전혀 없다.)

 

그러니 P를 중심으로 구분된 두 배열 집단의 차이는 R - sum == (total - sum) - sum인 것!

그래서 total에서 sum을 두 번 빼준것이다.

 

코드 수정 후 결과는?!!

 

드디어 퍼포먼스도 100%가 나왔다.

그리고 시간 복잡도도 O(n)으로 나와 이중 for문보다 훨씬 효율적이라는 것을 확인할 수 있었다.

 

다른 사람의 풀이

class Solution {
    public int solution(int[] A) {
        int[] dp = new int[A.length+3];
        final int len = A.length;
        dp[0] = A[0];

        for(int i=1 ; i<len ; i++) {
            dp[i] = dp[i-1] + A[i];
        }

        int mini = Integer.MAX_VALUE;
        for(int i=1; i<len ; i++) {
            int left = dp[i-1];
            int right = dp[len-1]-dp[i-1];
            int temp = Math.abs(left - right);
            mini = Math.min(temp,mini);
        }
        return mini;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

다른 사람의 코드를 찾아보다가 코드가 조금 복잡해 보이지만 이런 알고리즘도 있다는 것을 학습하고 싶어 가져왔다.

이 사람은 DP(동적 계획법)을 통해 테스트를 해결했다고 한다.

 

먼저 배열 dp에 index에 따른 합계를 계산해준다.

그리고 임의의 숫자 P에 따라 구분된 배열의 값을 dp 배열에서 꺼내 최소값을 계산한다.

 

'풀이 - 2'에 비해 소스코드가 조금 더 복잡해 보인다.

하지만 결과에서 알 수 있듯이 DP 또한 효율적인 알고리즘임은 틀립없다.

코딩테스트 뿐만 아니라 알고리즘 공부를 위해서라도 DP에 대해 알아두면 좋을 것 같다.