TapeEquilibrium

TapeEquilibrium 문제

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

요약

sumFirstPart (A[0] ~ A[P - 1] 까지의 합) 과 sumSecondPart (A[P] ~ A[N - 1] 의 합) 을 뺀 후에 절대값을 씌운다. 그 값들 중 가장 작은 값을 return 해라!

풀이과정

일단 무식하게 코드를 짜보았습니다. 반복문이 테이프 전체를 돌면서 sumFirstPart 값과 sumSecondPart 값을 유지해야했기에 for 이중루프를 사용했습니다.

int N = A.length;
int minDifference = Integer.MAX_VALUE;
  
for (int P = 1; P < N; P++) {
    long sumFirstPart = 0;
    for (int i = 0; i <= P - 1; i++) {
        sumFirstPart += A[i];
    }
    long sumSecondPart = 0;
    for (int j = P; j <= N - 1; j++) {
        sumSecondPart += A[j];
    }
    int difference = (int) Math.abs(sumFirstPart - sumSecondPart);
    minDifference = Math.min(minDifference, difference);
    }
    return minDifference;
    

이렇게 코드를 짜니 O(n^2) 형태의 코드가 나왔습니다. 테스트를 돌려볼까요?

int[] A = new int[200000000];

for (int i = 0; i < 200000000; i++) {
    A[i] = i;
}
TapeEquilibrium tapeEquilibrium = new TapeEquilibrium();
long start = System.currentTimeMillis();
int actual = tapeEquilibrium.solutionTry01(A);
long end = System.currentTimeMillis();
System.out.println("실행시간 ["+((end - start)/1000.0)+"]");
System.out.println(actual);

가장 큰 입력값을 만들기위해서 Index 크기를 Integer.MAX_VALUE (= 2^31 - 1) 로 했더니 java.lang.OutOfMemoryError: Requested array size exceeds VM limit 에러가 떴습니다.. 생각해보니까 int = 4byte 계산기 뚜드려 봤더니 8GB 를 잡으려고했던 것이었습니다. 내가 지금 Intellij 에 잡은 VM 힙 사이즈가 2GB 밖에 안되는데 8GB 를 잡으려했으니 이 메세지가 뜨는 게 당연합니다. 그래서 800MB 정도면 안전빵으로 내 PC 에서 적당히 큰 입력값을 만들어낼 것 같아서 계산해보니까 200000000 요걸로 한번 돌려봤는데요 200000000 이것도 5분 기다렸는데 안끝나서 0 하나를 빼보았습니다.. 그러면 80MB 정도되겠죠? 80MB 도 20분이나 기다렸는데도 구하지못했습니다.. 결과를 보는 것은 포기 ㅠㅠ

이제 제 목표는 이 코드를 O(logN) 형식으로 변환하는 것입니다!

int N = A.length;
long total = 0;
long sumFirstPart = 0;
int minDifference = Integer.MAX_VALUE;
long sumSecondPart = 0;

for (int i = 0; i < N; i++) {
    total += A[i];
    }

int sumFirstPartArray[] = new int[N];
sumFirstPartArray[0] = 0;

for (int P = 1; P < N; P++ ) {
    sumFirstPartArray[P] = sumFirstPartArray[P-1] + A[P];
    }

for (int P = 1; P < N; P++ ) {
    sumSecondPart = total - sumFirstPartArray[P];
    int difference = (int) Math.abs(sumFirstPartArray[P] - sumSecondPart);
    minDifference = Math.min(minDifference, difference);
    }
return minDifference;

모두 따로 변수로 빼고 for 문을 각자! 돌렸더니 아주 잘 해결했습니다. 각자 결과 값도 유지되고 이중 루프도 돌지 않게되니 최상의 코드가 나온 것 같습니다.