Codility Lesson 15 - MinAbsSumOfTwo

문제 설명

A를 N개의 정수로 구성된 비어 있지 않은 배열이라고 가정합니다.

한 쌍의 인덱스(P, Q)에 대한 둘의 내적합은 0 ≤ P ≤ Q < N에 대해 절대값 |A[P] + A[Q]|입니다.

예를 들어, 다음 배열 A:

  A[0] = 1
  A[1] = 4
  A[2] = -3

에는 (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)의 인덱스 쌍이 있습니다.

• (0, 0) 쌍에 대한 2의 합은 A[0] + A[0] = |1 + 1| = 2입니다.
• (0, 1) 쌍에 대한 2의 내적합은 A[0] + A[1] = |1 + 4| = 5입니다.
• (0, 2) 쌍에 대한 2의 내적합은 A[0] + A[2] = |1 + (-3)| = 2입니다.
• (1, 1) 쌍에 대한 2의 내적합은 A[1] + A[1] = |4 + 4| = 8입니다.
• (1, 2) 쌍에 대한 2의 내근 합은 A[1] + A[2] = |4 + (-3)| = 1입니다.
• (2, 2) 쌍에 대한 2의 내적합은 A[2] + A[2] = |(-3) + (-3)| = 6입니다.
• 함수를 작성합니다:

function solution(A);

이 함수는 N개의 정수로 구성된 비어 있지 않은 배열 A가 주어졌을 때 이 배열의 모든 인덱스 쌍에 대해 2의 최소합을 반환합니다.

예를 들어 다음 배열 A가 주어집니다:

  A[0] = 1
  A[1] = 4
  A[2] = -3

이면 위에서 설명한 대로 함수는 1을 반환해야 합니다.

배열 A가 주어졌습니다:

  A[0] = -8
  A[1] = 4
  A[2] = 5
  A[3] =-10
  A[4] = 3

이면 함수는 |(-8) + 5| = 3을 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성합니다:

• N은 [1..100,000] 범위 내의 정수입니다;
• 배열 A의 각 요소는 [-1,000,000,000..1,000,000,000] 범위 내의 정수입니다.

문제 접근

투포인터 이용

1. 배열을 오름차순으로 정렬
2. left + right 가 0 보다 작으면 왼쪽이 음수라는 의미 왼쪽 위치++
3. left + right 가 0 보다 크면 오른쪽 값이 더 크다는 의미이므로 오른쪽 위치—
4. 해당 배열을 순회하면서 가장 작은값을 찾는다.
5. 합계가 0 이면 return
6. 반복문은 왼쪽 인덱스가 오른쪽인덱스를 따라잡거나 보다 커질때 까지 반복문을 순회한다.
7. 교차한다는 의미는 전체 배열을 모두 순회했다는 뜻이다.

function solution(A) {
    const arr = A.slice().sort((a, b) => a - b);

    let left = 0;
    let right = A.length - 1;
    let minSum = Number.MAX_SAFE_INTEGER;

    while (left <= right) {
        let sum = arr[left] + arr[right];

        minSum = Math.min(minSum, Math.abs(sum));

        if (sum === 0) {
            break;
        }

        if (sum < 0) {
            left++;
        } else {
            right--;
        }
    }

    return minSum;
}