Lesson 15. Caterpillar method - MinAbsSumOfTwo #2 (속도 개선-1)

1. 속도 개선 아이디어

정렬을 통해 계산 횟수를 줄일 수 있다.

데이터가 오름차순으로 정렬되어 있으면

최소값 ----------------- 최대값 순으로 나열되어 있다.

 

index i는 0번째(최소값)에서 시작하고,

index j는 n-1번째(최대값)에서 시작해서, j 값을 줄여가면서(j--) 절대값을 찾는다면,

index i에서의 최소값을 구할 수 있다.

특히, 절대값이 어느 순간 커진다면, 중간에 탐색을 멈출 수 있다.

 

예시)

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]
-10	8	9	10	11	12	13

 

A[0] + A[6] = |(-10) + 13| = 3

A[0] + A[5] = |(-10) + 12| = 2

A[0] + A[4] = |(-10) + 11| = 1

A[0] + A[3] = |(-10) + 10| = 0

A[0] + A[2] = |(-10) + 9| = 1 → 이전 결과 값 보다 커졌다. 반복문 종료.

 

2. 코드 (C++)

#include <algorithm>

int solution(vector<int> &A) {

    sort(A.begin(), A.end());

    int min = numeric_limits<int>::max();
    for(int i = 0; i < (int)A.size(); i++)
    {
        int previous_result = numeric_limits<int>::max();
        for(int j = (int)A.size() - 1; j >= i; j--)
        {
            int sum = A[i] + A[j];
            if(sum < 0) sum *= -1;
            
            if(sum > previous_result) break;
            previous_result = sum;

            if(sum < min) min = sum;
        }
    }

    return min;
}

 

 

3. 결과

속도가 빨라 졌으나, 결과는 같다.