Lesson 15. Caterpillar method - MinAbsSumOfTwo #4 (속도 개선-3)

1. 속도 개선 아이디어

지금까지 모든 반복문은 항상 시작위치가 정해져 있었다.

최소값: 0번째부터 시작

최대값: (N - 1)번째부터 시작

 

그런데 꼭 이렇게 끝에서부터 검색을 해야 할까? 

Vector A의 요소들 간에 값 차이가 매우 클수도 있지만, 만약 매우 오밀조밀하다면?

처음부터 다시 찾지 말고, 이전에 찾은 최소 값을 기준으로 검색하는 것이 더 빠르다.

 

예시)

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

 

A[0] + A[7] = |(-10) + 15| = 5

A[0] + A[6] = |(-10) + 14| = 4

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

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

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

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

 

이전에 찾은 최소값 index(3)부터 검색을 시작한다.

A[1] + A[3] = |(-7) + 9| = 2 → 현재 index 3

 

여기서 검색방향을 확인하기 위해, 현재 index의 왼쪽(-1)과 오른쪽(+1) 값을 같이 확인한다.

A[1] + A[4] = |(-7) + 12| = 5

A[1] + A[2] = |(-7) + 8| = 1 → 현재 index 보다 왼쪽으로 이동했을 때, 값이 줄어든다. (왼쪽으로 탐색해서 최소값을 찾는다)

	index i
A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]
-10	-7	8	9	12	13	14	15
		index j - 1	index j	index j + 1
		절대값 1	절대값 2	절대값 5
index j - 1 이 가장 작은 결과값을 가지므로, 왼쪽방향으로 탐색을 시작

 

만약 현재 index j가 가장 작은 절대값을 가진다면, 추가 탐색이 필요 없다.

 

2. 코드 (C++)

#include <algorithm>

int solution(vector<int> &A) {
    
    vector<int> positive_numbers = {};
    vector<int> negative_numbers = {};

    for(size_t i = 0; i < A.size(); i++)
    {
        if(A[i] > 0) positive_numbers.emplace_back(A[i]);
        else if(A[i] < 0) negative_numbers.emplace_back(A[i]);
        else return 0;
    }

    sort(positive_numbers.begin(), positive_numbers.end());
    sort(negative_numbers.begin(), negative_numbers.end());

    //remove duplicates
    auto last = unique(positive_numbers.begin(), positive_numbers.end());
    positive_numbers.erase(last, positive_numbers.end());

    last = unique(negative_numbers.begin(), negative_numbers.end());
    negative_numbers.erase(last, negative_numbers.end());

    if(positive_numbers.empty()) //A has only negative numbers;
    {
        return (negative_numbers.back() * 2) * -1;
    }
    else if(negative_numbers.empty()) //A has only positive numbers;
    {
        return positive_numbers.front() * 2;
    }

    int min = numeric_limits<int>::max();
    int pos = 0;
    for(int i = 0; i < (int)negative_numbers.size(); i++)
    {
        while(0 <= pos && pos < (int)positive_numbers.size())
        {
        	//calculate the absolute value from the current index(pos)
            int mid = negative_numbers[i] + positive_numbers[pos];
            if(mid < 0) mid *= - 1;

            //init left and right value
            int left = numeric_limits<int>::max();
            int right = numeric_limits<int>::max();

            //calculate the absolute value at the current index(pos) -1
            if(pos - 1 >= 0)
            {
                left = negative_numbers[i] + positive_numbers[pos - 1];
                if(left < 0) left *= - 1;
            }

            //calculate the absolute value at the current index(pos) +1
            if(pos + 1 < (int)positive_numbers.size()) 
            {
                right = negative_numbers[i] + positive_numbers[pos + 1];
                if(right < 0) right *= - 1;
            }

            //decide on search path
            if(left < mid)
            {
                if(left < min) min = left;
                pos--;
            }
            else if(right < mid)
            {
                if(right < min) min = right;
                pos++;
            }
            else // mid < left && mid < right
            {
                if(mid < min) min = mid;
                break;
            }
        }
    }

    return min;
}

 

 

3. 결과