[백준] Node.js / 3273 - 두 수의 합 (투 포인터)

투 포인터(Two Pointers) 알고리즘

3273번: 두 수의 합

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

 

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

 

예제 입력 

9
5 12 7 10 9 1 2 3 11
13

 

예제 출력

3

 

나의 풀이

• 먼저 주어진 배열을 오름차순으로 정렬해준다.

• 투 포인터를 지정해준다. start는 인덱스 0, end는 마지막 인덱스로 지정한다. 

• 두 쌍의 합이 x 와 같다면 count와 start를 ++ 해준다.
• 두 쌍의 합이 x보다 크면 큰 쪽에서 값을 뺀다 (end--)
• 두 쌍의 합이 x보다 작으면 작은 쪽에서 값을 더한다 (start++)
• 두 포인터의 인덱스가 같으면, 더이상 계산할 쌍이 없다는 것이므로 계산을 마친다.

 

이 과정을 표현하면 다음과 같다.

 

 

코드

const input = require("fs")
  .readFileSync("../input.txt")
  .toString()
  .trim()
  .split("\n");

const n = Number(input[0]);
const arr = input[1]
  .trim()
  .split(" ")
  .map((x) => Number(x))
  .sort((a, b) => a - b);
const x = Number(input[2]);

let count = 0;
let sum = 0;
let start = 0;
let end = n - 1;

while (start !== end) {
  sum = arr[start] + arr[end];
  if (sum === x) {
    count++;
    start++;
  } else if (sum > x) {
    end--;
  } else {
    start++;
  }
}

console.log(count);