1253 좋다

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

=====

문제 풀이

특정 인덱스를 기준으로 삼고 원소에서 두개씩 빼내가며 합을 구한 뒤 인덱스 조정을 통해 계산을 최적화하면 되는 문제이다.

처음에는 원소가 양수만 온다는 것으로 착각하여 입력 배열을 오름차순으로 정렬한 뒤 

left =0 ,  right = idx-1 로 두고 이 인덱스에 위치한 값들의 합이 찾을려는 수보다 크다면 right--, 작다면 left++을 해주었다.

하지만 원소는 절대값 10억 이하였었다. 이 조건이 처리해주기 위해서는 left를 0 right를 n-1로 두어 전체 배열을 탐색할 필요가 있었다.

또한 전체 배열을 탐색하는 것이므로 지금 기준이 되는 인덱스가 left, right와 겹치면 안되므로 이것 또한 처리가 필요했다.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1]
    .split(' ')
    .map(BigInt)
    .sort((a, b) => {
        if (a > b) return 1;
        return -1;
    });
// N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
//
// N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
//
// 수의 위치가 다르면 값이 같아도 다른 수이다.
const decideGood = (idx) => {
    const bigValue = arr[idx];
    let left = idx === 0 ? 1 : 0;
    let right = idx === n - 1 ? n - 2 : n - 1;

    while (left < right) {
        const sumValue = arr[left] + arr[right];
        if (sumValue === bigValue) {
            return true;
        }
        if (sumValue > bigValue) {
            right--;
            if (right === idx) right--;
        } else {
            left++;
            if (left === idx) left++;
        }
    }
    return false;
};

let answer = 0;
for (let i = 0; i < n; i++) {
    const isGood = decideGood(i);
    if (isGood) answer++;
}

console.log(answer);