Lesson 15. Caterpillar method - MinAbsSumOfTwo #5

이미 100%를 달성했지만, 좀 더 좋은 코드로 만들어보자.

 

1. 문제에 대한 고찰

이 문제에서 요구하는 값은 결국 0이다.

물론 0이 나올지 안나올지는 알 수 없으나, 나오고 안나오고의 문제는 접어두고, 단순히 최적의 해가 무엇이냐 하면 0이다.

즉, 절대값이 0에 가까워 지도록, 계산해야할 값들을 선택하면 된다.

 

예시)

left							right
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 

5는 0보다 크다 →  0에 더 가깝게 만들기 위해서는 최대값을 더 작게(right - 1) 만들어야 한다.

 

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

4는 0보다 크다 →  0에 더 가깝게 만들기 위해서는 최대값을 더 작게(right - 1) 만들어야 한다.

 

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

3은 0보다 크다 →  0에 더 가깝게 만들기 위해서는 최대값을 더 작게(right - 1) 만들어야 한다.

 

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

2는 0보다 크다 →  0에 더 가깝게 만들기 위해서는 최대값을 더 작게(right - 1) 만들어야 한다.

 

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

-1은 0보다 작다 →  0에 더 가깝게 만들기 위해서는 최소값을 더 크게(left + 1) 만들어야 한다.

 

A[1] + A[3] = (-7) + 9 = 2

2는 0보다 크다 →  0에 더 가깝게 만들기 위해서는 최대값을 더 작게(right - 1) 만들어야 한다.

 

A[1] + A[2] = (-7) + 8 = 1

1은 0보다 크다 →  0에 더 가깝게 만들기 위해서는 최대값을 더 작게(right - 1) 만들어야 한다.

 

A[1] + A[1] = (-7) + (-7) = -14

index가 같아졌다. 탐색 종료.

 

2. 코드 (C++)

#include <algorithm>

int solution(vector<int> &A) {

    sort(A.begin(), A.end());    
    if(A.front() < 0 && A.back() < 0)
    {
        return (A.back() * 2) * -1;
    }
    else if(A.front() > 0 && A.back() > 0)
    {
        return A.front() * 2;
    }

    int min = numeric_limits<int>::max();
    int left = 0;
    int right = A.size() - 1;
    while(left <= right)
    {
        int l_value = A[left];
        int r_value = A[right];

        int sum = l_value + r_value;
        if(sum < 0 ) sum *= -1;

        if(sum == 0) return 0;
        else if(sum < min) min = sum;

        if(l_value + r_value < 0) left++;
        else right--;
    }

    return min;
}

 

 

3. 결과