합이 0에 가장 가까운 구간 / 알고리즘 문제해결전략 2권

이번 포스팅은 알고리즘 문제해결전략 2권의 601페이지에 나오는 '합이 0에 가장 가까운 구간' 예제 입니다.
자바 코드 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/%ED%95%A9%EC%9D%B4%200%EC%97%90%20%EA%B0%80%EC%9E%A5%20%EA%B0%80%EA%B9%8C%EC%9A%B4%20%EA%B5%AC%EA%B0%84/src/Main.java

우선 제목에서 가장 '가까운 구간' 이라고 해서, 책의 내용이 구간을 찾는 풀이로 오해 하실 수 있습니다. 책에 있는 내용은, 0에 가장 가까운 구간합을 찾는 것입니다. 여기서는 합이 0에 가장 가까운 구간도 함께 찾아 보겠습니다.

이 문제는 구간합(prefixsum)을 활용하는 방법을 배울 수 있는 문제입니다.

O(NlogN)에 관한 책의 설명을 좀더 보충해서 설명하자면, prefix sum을 구하고 정렬을 한뒤, 0에 가까운 구간을 찾으면, O(NLogN)이 됩니다.

• O(N)은 구간합을 계산할 때, 걸리는 시간 복잡도 이구요,
• O(NlogN)은 prefixSum을 정렬하는대 걸리는 시간 복잡도 이구요,
• O(N)은 정렬된 prefixSum에서, 0에 가장 가까운 구간합을 찾을 때, 걸리는 시간 복잡도 입니다.
• 따라서, O(N)은 없어지고 보다 큰 시간 복잡도인, O(NlogN)만 남습니다.

보다 설명할 부분은 prefix sum을 정렬을 하면, 어떻게 O(N)만에 0에 가장 가까운 구간합을 얻을 수 있느냐? 입니다.
구간합이 0에 가장 가까우려면, 2개의 임의의 구간합이 있다고 할 때, 둘의 차이가 가장 작을 수록, 0에 가까울수 있습니다.

구간합과는 아무런 관계없이, 정렬을 하게 되면 얻을 수 있는 특성이 있습니다. 즉, 어떤 수의 집합을, 각 수의 크기로 정렬을 하게 되면, 서로 인접한 숫자는, 그 집합의 어떤 숫자와 비교하더라도, 인접한 두수의 차이가 가장 적게 됩니다.
이 특성을 활용해서, min(pSum[i] - pSum[i-1])이 최소가 되는 값을 찾으면, 합이 0에 가장 가까운 구간합을 찾을 수 있습니다.

아래 구현에서는 추가적으로 실제로, 구간도 찾아 보았습니다.
Pair의 key 부분에는 배열의 index를, value부분에는 index까지 구간합을 저장하고, 샘플입력을 아래와 같이 했을 때, pairs가 value기준으로 소팅된 모습은 아래와 같습니다.

샘플입력

10
-14 7 2 3 -8 4 -6 8 9 11

pairs의 소팅 결과

위의 캡처의 선택된 부분, 즉, pSum[5] - pSum[1] 값이, 0에 가장 가까운 구간합이므로, 구간은 인덱스로 2~5 까지 입니다.

코드 주요 부분

public class Main {
    int N;
    int[] dt;
    int[] pSum;

    public void solve() throws IOException {
        N = sc.nextInt();
        dt = new int[N];
        pSum = new int[N];
        Pair[] pairs = new Pair[N];

        dt[0] = sc.nextInt();
        pSum[0] = dt[0];
        pairs[0] = new Pair<Integer, Integer>(0, pSum[0]);

        for(int i=1; i<N; ++i) {
            dt[i] = sc.nextInt();
            pSum[i] = dt[i] + pSum[i-1];

            // 구간을 구하기 위해서, Pair에 key에 배열의 인덱스를, value에 prefix sum의 값을 저장한다.
            pairs[i] = new Pair<Integer, Integer>(i, pSum[i]);
        }

        Arrays.sort(pSum);
        // pari의 value기준으로 소팅하고
        Arrays.sort(pairs);

        // 합이 0에 가장 가까운 구간의 합을 구하는 방법
        int r = Math.abs(pSum[0]);
        for(int i=1; i<N; ++i) {
            r = Math.min(r, Math.abs(pSum[i] - pSum[i-1]));
        }
        println(r);

        println();

        // 합이 0에 가장 가까운, 구간을 구하는 방법
        r = Math.abs((Integer)pairs[0].getValue());
        int k1 = -1;
        int k2 = -1;
        for(int i=1; i<N; ++i) {
            int t = r;
            t = Math.min(t, Math.abs((Integer)pairs[i].getValue() - (Integer)pairs[i-1].getValue()));

            // 보다 구간의 합이 0에 가까운 구간을 찾았으면,
            // 구간을 k1과 k2에 저장함
            if(t != r) {
                k1 = (Integer)pairs[i].getKey();
                k2 = (Integer)pairs[i-1].getKey();
                r = t;

                if(k1<k2)
                    k1++;
                else
                    k2++;
            }
        }

        println(r);
        println(k1 + "~" + k2);
    }
}