[백준3151_자바스크립트(javascript)] - 합이 0

🔴 문제

합이 0

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
const n = +inputs[0];
const A = inputs[1]
  .split(' ')
  .map(Number)
  .sort((a, b) => a - b);

let ans = 0;
const twoPointer = (target, start, end) => {
  let left = start;
  let right = end;

  while (left <= right) {
    const sum = A[left] + A[right] + target;

    if (sum < 0) left += 1;
    else if (sum > 0) right -= 1;
    else {
      if (A[left] === A[right]) {
        ans += ((right - left) * (right - left + 1)) / 2;
        break;
      }

      let leftCnt = 1;
      while (left + 1 < right && A[left] === A[left + 1]) {
        left += 1;
        leftCnt += 1;
      }

      let rightCnt = 1;
      while (right - 1 > left && A[right] === A[right - 1]) {
        right -= 1;
        rightCnt += 1;
      }

      ans += leftCnt * rightCnt;
      left += 1;
      right -= 1;
    }
  }
};

for (let i = 0; i < n - 2; i++) {
  twoPointer(A[i], i + 1, n - 1);
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

투포인터으로 풀이했다.(답봄)

세 수의 합이 0이 되도록 푸는 문제기 때문에 수 하나를 고정해놓고 나머지 두개 의 값을 옮겨가며 풀었다.

for (let i = 0; i < n - 2; i++) {
  twoPointer(A[i], i + 1, n - 1);
}

위의 코드를 보면 i번째 수를 고정된 수로 두는 것이다.
그럼 i+1과 n-1을 시작점, 끝점으로 잡고 이분탐색 해 세 수의 합이 0이 되는 경우를 찾으면 된다.

const sum = A[left] + A[right] + target;

이렇게 정해진 sum을 0과 비교하면 된다.

if (sum < 0) left += 1;
else if (sum > 0) right -= 1;

이렇게 sum이 0보다 작거나 0보다 큰 경우 left, right의 포인터를 옮겨준다.

else {
  if (A[left] === A[right]) {
    ans += ((right - left) * (right - left + 1)) / 2;
    break;
  }

  let leftCnt = 1;
  while (left + 1 < right && A[left] === A[left + 1]) {
    left += 1;
    leftCnt += 1;
  }
  
  let rightCnt = 1;
  while (right - 1 > left && A[right] === A[right - 1]) {
	right -= 1;
    rightCnt += 1;
  }

  ans += leftCnt * rightCnt;
  left += 1;
  right -= 1;
}

이제 sum이 0이어서 목표한 값을 찾는 로직이다.
이 때 A[left] 값과 A[right]값이 같다면 A[left]와 A[right]를 포함한 사이 값이 모두 같은값이라는 의미이다
이는 right - left + 1 개중 두 개를 순서 상관없이 고르는 조합 경우를 고려해주면 된다.

만약 두 값이 같지 않다면 왼쪽 포인터 좌표의 중복값을 고려해줘야 하는데,
left+1 이 right보다 작고(범위 체크),A[left]값이 A[left+1]값과 같다면
left포인터 값을 옮겨주고, leftCnt를 1증가시켜준다.

right도 마찬가지로 처리해주면 left, right의 개수가 나오는데 이 둘의 곱만큼 팀을 만들 수 있다.

중복처리를 다 했으면 left 값과 right값이 다음 포인터를 가르킬 수 있도록 옮겨주면 된다.

🔵 Ref