Table of contents

코딜리티 TapeEquilibrium

N 사이즈의 배열 A를 P번 순회하면서 (0 < P < N), |sum(A[0]...A[P - 1]) - sum(A[P]...A[N - 1])|가 최소인 값을 구하는 문제이다. 즉, 배열을 순회하면서 P를 기준으로 좌측의 배열의 합과, 우측의 배열(P번쨰 요소 포함)의 합의 차이의 절대값을 구하면서 최소값을 찾는 문제이다.

첫번째 풀이

O(N**2) = O(N^2)

private int minDiffAboutTapes(int[] A) {
    int N = A.length;
    int min = Integer.MAX_VALUE;
    int count = 0;
    for (int P = 1; P < N; P++) {
        int sumP = 0;
        int sumN = 0;
        for (int i = 0; i < P; i++) {
            sumP += A[i];
        }
        for (int i = P; i < N; i++) {
            sumN += A[i];
        }

        int diff = Math.abs(sumP - sumN);
        if (++count % 3 == 0) System.out.println();
        if (min > diff) {
            min = diff;
        }
    }
    return min;
}

앞서 언급한대로 배열을 순회하면서 (P는 1이상), P를 기준으로 좌측, 우측 배열의 합의 차이를 절대값으로 저장한 뒤, 이전 단계의 최소값과 비교 후, 최소값을 갱신한다.

두번째 풀이 (합을 한번만 구하기)

O(N)

코드를 보기 전에, 문제에서 주어진 예제를 단계적으로 분석해보자.

A[0] = 3, A[1] = 1, A[2] = 2, A[3] = 4, A[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

먼저, 아래와 같이 두개의 sum 변수와, a라는 변수가 있다고 생각해보자.

sumToP = sum(A[0]...A[P - 1]), sumToN = sum(A[P]...A[N - 1])

a = A[P - 1]

  • P = 1: a = 3, sumToP = 3, sumToN = 10
  • P = 2: a = 1, sumToP = 4 (3 + 1), sumToN = 9 (10 - 1)
  • P = 3: a = 2, sumToP = 6 (4 + 2), sumToN = 7 (9 - 2)
  • P =4: a = 4, sumToP = 10(6 + 4), sumToN = 3 (7 - 4)

단계가 진행될 때마다 sumToP는 이전 단계의 sumToP 값에 A를 더한 값이 되고, sumToN는 이전 단계의 sumToN 값에서 A를 뺀 값이 된다.

P = 1 일 때, sumToP[P] = A[0], sumToN= sum(A[1]...A[N - 1])

P > 1 일 때, sumToP[P] = sumToP[P - 1] + A[P - 1], sumToN= sumToN[P - 1] - A[P - 1]

이러한 공식을 사용한다면 단계마다 합을 다시 계산할 필요가 없게된다.

public int diffAboutTapes(int[] A) {
    int N = A.length;

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

    int min = Math.abs(sumToP - sumToN);

    for (int P = 2; P < N; P++) {
        sumToP += A[P - 1];
        sumToN -= A[P - 1];

        int diff = Math.abs(sumToP - sumToN);
        if (diff < min) {
            min = diff;
        }
    }
    return min;
}

정리

코딜리티에서 제공하는 PDF 파일에서 흥미로운 내용을 발견했다.

.....During contests, we are often given a limit on the size of  data, .....

• n <= 1 000 000, the expected time complexity is O(n) or O(n log n),
• n <= 10 000, the expected time complexity is O(n2),
• n <= 500, the expected time complexity is O(n3).

의역하자면 보통 데이터 크기의 제한이 주어지기 때문에 상한이 어느정도인지 예측할 수 있으므로 배열의 크기 제한 n과 상한의 관계가 아래와 같다고 한다.

  • 배열의 크기 제한이 500이하인 경우 O(n^3)
  • 배열의 크기 제한이 10000이하인 경우 O(n^2)
  • 배열의 크기 제한이 백만 이하인 경우 O(n) 혹은 O(n log n)

이 문제에서는 배열의 크기 N이 2 < N < 100,000의 범위를 갖는다. 그러므로 O(n) 혹은 O(n log n) 복잡도를 가져야 하는데 첫번째 해결법은 O(n^2)이기 때문에, N이 100만 넘어가도 타임아웃이 발생했다.