3151 합이 0 (자바스크립트)

문제

Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.

Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 Ai는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라.

N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하여라.

입력

입력은 표준 입력으로 주어진다.

첫 번째 줄에 학생의 수 N이 입력된다. 두 번째 줄에 N개의 그녀가 가르칠 학생들의 코딩 실력인 Ai가 주어진다.

출력

표준 출력으로 그녀가 고를 수 있는 팀의 수를 하나의 정수로 출력한다.

====

문제 분석

이전 세 용액 문제처럼 하나의 Pivot을 세우고 그것을 기준으로 s와 e를 둔 뒤에 합에 따라 s를 +1 또는 e를 -1 해줬다.

하지만 sum이 0이라면 s와 e중 어떤 값을 움직일지 판단하기 어려웠다.

만약 s의 다음 값이 s와 같다면 굳이 덧셈을 하지 않아도 0이 나올테니 s가 s+1의 값과 같지 않을 때까지 s++를 해주거나

e의 이전 값이 e와 같다면 이또한 굳이 덧셈을 하지 않아도 0이 나올테니 e와 e-1의 값과 같지 않을 때까지 e--를 해준다.

여기에서 만약 arr[s]와 arr[e]이 같다면 오름차순으로 나열되어 있는 배열에서 중간값들은 결국 arr[s] arr[e]와 같은 값이 나온다.

따라서 덧셈을 하지 않더라도 sum이 0이라면 가운데 놈들 또한0 이 나오므로 여기에서 나올 수 있는 조합의 경우수인

nC2 를 계산하여 answer에 더해준다. --->(n*(n-1))/2

만약 sum이 0보다 작다면 더 큰 값을 더해주기 위해 s++

반대라면 e--를 해주면 된다.

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(Number)
    .sort((a, b) => a - b);

let answer = 0n;

for (let pivot = 0; pivot < n - 2; pivot++) {
    let s = pivot + 1;
    let e = n - 1;

    while (s < e) {
        const sum = arr[pivot] + arr[s] + arr[e];
        if (sum === 0) {
            if (arr[s] === arr[e]) {
                const count = e - s + 1;
                answer += BigInt((count * (count - 1)) / 2);
                break;
            }

            let leftCount = 1;
            let rightCount = 1;

            while (s + 1 < e && arr[s] === arr[s + 1]) {
                leftCount++;
                s++;
            }

            while (e - 1 > s && arr[e] === arr[e - 1]) {
                rightCount++;
                e--;
            }
            answer += BigInt(leftCount * rightCount);
        }
        if (sum <= 0) {
            s++;
        } else {
            e--;
        }
    }
}

console.log(answer.toString());