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

1. 속도 개선 아이디어

Vector A에서 음수와 양수를 분리해보자.

'음수 + 음수', '양수 + 양수'와 같은 불필요한 연산을 줄일 수 있다.

또한 Vector A가 음수 혹은 양수로만 구성되어 있을 경우, 정렬을 통해 별도 검색없이 바로 결과를 도출할 수 있다.

(음수로만 구성되어 있을 경우, return (최대값 * 2) * -1)

(양수로만 구성되어 있을 경우, return (최소값 * 2)) 

 

2. 코드 (C++)

최소값을 찾는 로직은 이전과 동일하다.

#include <algorithm>

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

    //split the positive and 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());

    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();
    for(int i = 0; i < (int)negative_numbers.size(); i++)
    {
        int previous_result = numeric_limits<int>::max();
        for(int j = 0; j < (int)positive_numbers.size(); j++)
        {
            int sum = negative_numbers[i] + positive_numbers[j];
            if(sum < 0) sum *= -1;

            if(previous_result < sum) break;
            previous_result = sum;

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

    return min;
}

 

 

3. 결과